Information Technology Reference
In-Depth Information
OPT
(
I
). On the other hand,
there is a straightforward plan for
I
with cost
OPT
(
I
)+
n
and we conclude the
following:
From Lemma 1 we conclude that
OPT
(
I
)+
n
≤
OPT
(
I
)=
OPT
(
I
)+
n.
(1)
n
4
since a vertex cannot dominate
more than 3 vertices. From (1) we now see that
The graph in
I
is cubic implying
OPT
(
I
)
≥
OPT
(
I
)
≤
5
OPT
(
I
)
(2)
showing that condition 1 for
L
-reductions from Sec. 1.2 is satisfied with
α
=5.
From Lemma 1 and (1) we finally conclude that
cost
(
y
)
OPT
(
I
)
cost
(
x
)
−
OPT
(
I
)
≤
−
(3)
showing that condition 2 for
L
-reductions from Sec. 1.2 is satisfied with
β
=1.
This shows that
f
and
g
realize a
L
-reduction and we conclude that PRIVATE-
PARK-AND-RIDE-UNW-4 is APX-complete since this is the case for MIN-
DOM-SET-CUBIC.
The result stated by Theorem 3 also holds restricted to low-coordination plans.
Finally, we mention one direction for future work. As mentioned in Sec. 1.1
the problem of computing an optimal park-and-ride-plan generalizes the Steiner
tree problem. It thus seems natural to consider the possibility of generalizing
the well known Dreyfus-Wagner algorithm [9] for computing minimum weight
Steiner trees. One of the challenges - at least for the author — for doing this is
the existence of optimal plans requiring much coordination.
References
1. Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theo-
retical Computer Science 237(12), 123-134 (2000)
2. Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and
hardness of approximation problems. In: Proceedings of the 33rd Annual Sympo-
sium on Foundations of Computer Science, pp. 14-23 (1992)
3. Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P.,
Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems
and Their Approximability Properties. Springer, New York (1999)
4. Baldacci, R., Maniezzo, V., Mingozzi, A.: An exact method for the car pooling
problem based on lagrangean column generation. Operations Research 52(3), 422-
439 (2004)
5. Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Infor-
mation Processing Letters 32(4), 171-176 (1989)
6. Charikar, M., Chekuri, C., Cheung, T.-Y., Dai, Z., Goel, A., Guha, S., Li, M.: Ap-
proximation algorithms for directed Steiner problems. Journal of Algorithms 33(1),
73-91 (1999)
7. Chvatal, V.: A greedy heuristic for the set-covering problem. Mathematics of Op-
erations Research 4(3), 233-235 (1979)
