Information Technology Reference
In-Depth Information
t
t
t
t
Fig. 2.
Two workers have to travel to a neighbour vertex for the smallest possible
cost. The big circles correspond to states and the dashed arrows indicate leave- or
enter-transitions. The optimal plan has cost 1.
set cardinality bounded by
k
. For a given solution of the WEIGHTED SET
COVER instance we can eciently construct a low-coordination plan for the
PRIVATE-PARK-AND-RIDE instance with the same cost - or a lower cost if
the sets overlap (this is possible becauseallworkershaveacarwiththesame
capacity). The WEIGHTED SET COVER problem admits a polynomial time
H
(
k
)-approximation algorithm if the set cardinality is bounded by
k
[7].
3 Inapproximability for Simple Graphs and Car Capacity 4
In this section we show that the PRIVATE-PARK-AND-RIDE problem is APX-
complete when restricted to cars with capacity 4 and unweighted and undirected
graphs meaning that all edges have cost 1. We give this problem a special name:
Definition 2.
The PRIVATE-PARK-AND-RIDE-UNW-4 problem is the re-
striction of the PRIVATE-PARK-AND-RIDE problem to undirected unweighted
graphs (cost
(
e
)=1
for every edge e) and cars with capacity
4
.
Before introducing the problem that will form the starting point for our re-
duction we kindly remind the reader on some terminology: A cubic graph is a
graph where all vertices have exactly three neighbours and a dominating set of
agraph
G
(
V,E
) is a set of vertices
V
⊂
V
has
at least one neighbour in
V
. The following problem will form the basis for our
L
-reduction:
V
such that any member of
V
\
