Information Technology Reference
In-Depth Information
A feasible solution of the PRIVATE-PARK-AND-RIDE problem is a plan for
getting all the workers from their starting location to the target vertex t and the
objective is to compute a minimum cost plan. A plan is a sequence of no more
than p
(
)
steps where only the following steps are allowed and the cost of a plan
is the sum of the costs of the steps:
|
I
|
1. A car at vertex u can drive along the edge e
(
u,v
)
and transport the workers
in it to vertex v withacostofcost
(
e
)
.
2. A worker can leave a car at a vertex with a cost of
0
. A worker can only
leave his own car if no other workers are on board in which case the car can
not move anymore.
3. A worker can enter a car at a vertex if the capacity of the car allows it. The
cost of such a move is
0
.
For our first result we examine the computational complexity for the case
where the number of workers is a fixed constant.
Theorem 1.
The PRIVATE-PARK-AND-RIDE problem can be solved in poly-
nomial time if
|
W
|
is a constant.
Proof.
We provide a sketch of the proof. We refer to a given distribution of
the workers and cars on the vertices as a
state
. We construct a state transition
graph where the transitions are the steps mentioned in Definition 1. We assign
a small cost to leaving and entering a car and the transition corresponding to
driving along an edge
e
is assigned the cost
cost
(
e
). We now find the solution by
computing the shortest path from the initial state to a goal state (all workers at
vertex
t
). A simple example with a part of the state transition graph is shown
in Fig. 2 where two workers have to travel to a neighbour vertex for the smallest
possible cost. The algorithm runs in polynomial time since the number of states
is bounded by a polynomial (
|
W
|
is constant).
In some situations, we maybe choose only to consider plans where a worker
w
only has to coordinate with the workers arriving to
t
in the same car as
w
and
we will refer to such a plan as a
low-coordination
plan. There are cases where the
optimal plan is not a low-coordination plan as can be seen from the example in
Fig. 3. We now present our second positive result where
H
(
k
)=
i
=1
k
denotes
the
k
-th harmonic number:
Theorem 2.
There is a polynomial time H
(
k
)
-approximation algorithm for the
PRIVATE-PARK-AND-RIDE problem restricted to low-coordination plans if all
cars have capacity k for some constant k.
Proof.
Once again, we provide a sketch of the proof. For each subset
S
of work-
ers satisfying
k
we can use the state transition technique from the proof
of Theorem 1 with
W
=
S
to examine whether the workers in
S
can coordi-
nate and arrive to
t
in the same car - and compute an optimal way of doing it
and the corresponding cost if it is possible. In this way we can solve our prob-
lem using a polynomial time reduction to WEIGHTED SET COVER [7] with
|
S
|≤
