Information Technology Reference
In-Depth Information
at their initial location in the proofs. Helmert et al. [11] study the computa-
tional complexity for several logistics problems related to our problem. Baldacci
et al. [4] propose an exact method based on integer programming for solving the
problem where a set of so-called
servers
can pick up one or more
clients
and
drive them to the same destination. Baldacci et al. do not allow “park-and-ride”
as an option and they solve instances with only a few hundred people involved.
Baldacci et al. also use an argument for NP-hardness relying on the fact that
the sets of servers and clients are disjoint.
The Steiner tree problem is the problem of computing a minimum cost tree
spanning a given set of vertices
V
⊂
V
- called
terminals
- in a graph
G
(
V,E
).
A fairly simple reduction shows that the problem we focus at in this paper gen-
eralizes the Steiner tree problem in the pretty unrealistic setting where the cars
have infinite capacity. This means that our problem is harder than the Steiner
tree problem if we allow cars with unlimited capacity. The reduction works by
letting one of the terminals be the common destination and put a car with un-
limited capacity and a person on every other terminal. Bern and Plassmann [5]
show that the Steiner tree problem is APX-complete for undirected complete
graphs with edge lengths 1 and 2 and Charikar et al. [6] argue that it is hard to
approximate the directed Steiner tree problem to a factor better than ln
k
where
k
is the number of terminals.
1.2 APX, PTAS and
L
-Reductions
We now give a very brief introduction to the complexity classes APX and PTAS
and
L
-reductions that will be used in Sec. 2 to prove our main result. We refer
to [3,8] for more details. A (1 +
)-approximation algorithm for a minimization
problem
Π
is an algorithm that, given any instance
I
of
Π
, computes a feasible
solution
x
to
I
with
cost
(
x
)
(1 +
)
OPT
(
I
)where
cost
denotes the objective
function and
OPT
(
I
) denotes the minimum achievable cost for instance
I
.The
problem
Π
is a member of the complexity class APX if the problem admits a
polynomial time (1 +
)-approximation algorithm for
some
constant
>
0. If
such an algorithm exists for
any >
0then
Π
is a member of the complexity
class PTAS (Polynomial Time Approximation Scheme).
The hardest members of APX are the so-called APX-complete problems. If
we could prove membership of PTAS for any APX-complete problem it would
imply APX = PTAS having NP = P as a consequence [2]. Analogously to the
NP/P-setting, we typically use reductions from problems known to be hard to
prove completeness and the
L
-reduction introduced by Papadimitriou and Yan-
nakakis [12] is often used. A problem
Π
can be reduced to
Π
using a
L
-reduction
written
Π
≤
≤
L
Π
if there are polynomial time functions
f
and
g
and constants
α
and
β
such that the following conditions hold:
1. The function
f
transforms any instance
I
of
Π
into an instance
f
(
I
)=
I
of
Π
such that
OPT
(
I
)
αOPT
(
I
).
2. The function
g
transforms any feasible solution
y
of
I
into a solution
x
of
I
such that
≤
OPT
(
I
)
cost
(
y
)
|
OPT
(
I
)
−
cost
(
x
)
|≤
β
|
−
|
.
