Information Technology Reference
In-Depth Information
t
Fig. 4.
The figure shows how an edge in
I
(on the left) is processed by the reduc-
tion. The circles and squares on the right correspond to
u
-vertices and
u
-vertices,
respectively.
the first visit of
w
after
w
leaving
loc
(
w
). We now define
U
in the following way:
U
=
. Please note that
w
may have been picked up by another
worker at
loc
(
w
) and made the first visit to
h
(
w
) as a passenger. We now define
x
as the set of vertices in
I
corresponding to
U
.Theset
x
is a dominating set
and thus a feasible solution for
I
-ifavertex
v
is not in the set
x
then one of
the
u
-vertices of the neighbours of
v
must have received the first visit of the
worker located at
v
. We now make a new and cheaper plan
y
∗
by letting all
workers
w
go
by their own car
to the vertex
h
(
w
). When all workers have moved
to their corresponding vertex in
U
the plan
y
∗
dictates them to share
one
car
and travel directly to
t
- it is possible to share one car since the graph defining
I
is cubic and all cars have capacity 4. It is not hard to see that
x
can be produced
in polynomial time and that the following holds
{
h
(
w
):
w
∈
W
}
n
+
cost
(
x
)=
cost
(
y
∗
)
cost
(
y
)
.
≤
Lemma 2.
PRIVATE-PARK-AND-RIDE-UNW-4
∈
APX.
Proof.
There is a simple polynomial time 4-approximation algorithm for
PRIVATE-PARK-AND-RIDE-UNW-4: Let all workers drive in their own car
along the shortest path from their location to
t
. This plan has total cost
w∈W
d
(
loc
(
w
)
,t
)where
d
(
u,v
) is the minimum distance from
u
to
v
in the
graph. If we imagine that all workers (including the driver) in a car share the
cost of driving along an edge evenly then we can see that
w∈W
d
(
loc
(
w
)
,t
4
is a
lower bound for the minimum achievable total cost of a plan since all workers
pay the minimum possible amount.
We are now ready to state and prove our main result:
Theorem 3.
The PRIVATE-PARK-AND-RIDE-UNW-4 problem is APX-
complete.
Proof.
Membership of APX is already established by Lemma 2. We now prove
that the functions
f
and
g
presented above can be used to prove that MIN-
DOM-SET-CUBIC
≤
L
PRIVATE-PARK-AND-RIDE-UNW-4.
