Information Technology Reference
In-Depth Information
t
Fig. 3.
An example of a PRIVATE-PARK-AND-RIDE instance where the optimal
plan is not a low-coordination plan. The workers indicated by black rectangles all have
a car with capacity 4 and all the edges have cost 1. The 4 workers to the right and the
2 workers to the left at the top have to coordinate to obtain an optimal plan with cost
6. The 2 workers at the bottom can be picked up by the 6 workers at the top if one of
the 4 workers to the right at the top changes car after driving along the first edge.
Definition 3.
An instance of the MIN-DOM-SET-CUBIC problem is a cubic
unweighted undirected graph G
(
V,E
)
and the solution is a dominating set V
⊂
V
with minimum cardinality (the cost of a feasible solution V
is
V
|
|
).
Alimonti and Kann [1] have shown that the MIN-DOM-SET-CUBIC problem is
APX-complete.
The main part of the remainder of this paper will be dedicated to showing
MIN-DOM-SET-CUBIC
≤
L
PRIVATE-PARK-AND-RIDE-UNW-4. We use the
notation from Sec. 1.2 so MIN-DOM-SET-CUBIC and PRIVATE-PARK-AND-
RIDE-UNW-4 will play the role of
Π
and
Π
, respectively. The first thing we
do is to show how to transform an instance
I
of MIN-DOM-SET-CUBIC into
an instance
f
(
I
)=
I
of PRIVATE-PARK-AND-RIDE-UNW-4. For each vertex
u
in
I
we add vertices
u
and
u
to
I
. We connect every
u
-vertex with the
corresponding
u
-vertex. We also add a target vertex
t
to
I
and connect
t
to
all the
u
-vertices. For each edge
in
I
we insert two edges in
I
:
u
,v
}
{
u,v
}
{
v
,u
}
and
. Figure 4 illustrates how an edge is transformed by the function
f
. Finally, we place a worker with a car with capacity 4 at each
u
-vertex. The
reader might benefit from thinking of the
u
-vertices as parking lots where the
workers can meet and share one car for the final ride to
t
. The following lemma
introduces the function
g
and expresses the crucial property the function has:
{
Lemma 1.
There is a polynomial time function g that for any feasible solution
y to I
produces a feasible solution x to I such that cost
(
x
)+
n
cost
(
y
)
where
≤
n is the number of vertices in I.
Proof.
Now assume that we are given a feasible solution
y
to
I
.Inotherwords,
y
is a plan containing a sequence of steps bringing all the workers to
t
.Foreach
worker
w
we let
h
(
w
) denote the vertex
u
that according to the plan
y
receives
