Information Technology Reference
In-Depth Information
If we have a polynomial time (1+
)-approximation algorithm for
Π
it is not hard
to use
f
and
g
and obtain a polynomial time (1+
αβ
)-approximation algorithm
for
Π
. This shows that an
L
-reduction preserves membership of PTAS in the
sense
Π
∈
PTAS. We can show that a problem
Π
is APX-
complete if we can prove the following for a problem
Π
known to be APX-
complete: 1)
Π
∈
PTAS
⇒
Π
∈
≤
L
Π
.
APX
and 2)
Π
1.3 Contribution and Outline
We formally define the PRIVATE-PARK-AND-RIDE problem in Section 2 and
establish a positive result when we restrict the problem to a constant number
of persons. We also present a positive result for the case where the capacity
of the cars is a fixed constant and where people only coordinate with their co-
passengers in the car arriving at the common destination. Finally, we present
our main result in Section 2 where we show that the problem is APX-complete
in the realistic setting where all cars have capacity 4 even restricted to simple
unweighted undirected graphs.
2 Preliminaries
In the following we refer to the persons involved in the PRIVATE-PARK-AND-
RIDE problem as workers and we might think of the common destination as
the workplace of the workers. We now formally define the problem of getting all
the workers to their workplace at a minimum cost if they all have a car at their
disposal and can pick each other up and drop each other any place. The costs
could be any combination of fuel costs, tolls, congestion charges, etc. It is intu-
itively clear that a polynomial
p
exists such that an optimal plan exists for any
instance
I
with a number of steps bounded by
p
(
) and this is the polynomium
we refer to below. Helmert [10] provides a relatively simple argument that such
a polynomial exists when he considers the more general case. As a technicality
the polynomial upper bound on the number of steps ensures membership of the
complexity class NPO for the problem. We are now ready to state the formal
definition of our problem.
|
I
|
Definition 1.
An instance of the PRIVATE-PARK-AND-RIDE problem is a
6
-tuple
(
G
(
V,E
)
,W,cap,cost,loc,t
)
where
-
G is a graph where V is the set of vertices in the transportation network and
E
V is a set of edges.
-
W is a set of workers. Every worker has a car at his disposal.
-
cap
:
W
⊆
V
×
→
N
. The car owned by worker w has capacity cap
(
w
)
.
+
. The cost of traveling along an edge e with a car is cost
(
e
)
.
-
cost
:
E
→
R
-
loc
:
W
V . The starting location of a worker w and the car owned by the
worker is loc
(
w
)
.
-
t
→
V is the target location for all workers. For each worker w there is a
path from loc
(
w
)
to t.
∈
