4
A time-slot is dened to be those instants of time over which all edge lengths
are invariant. We assume that time can b e partitioned into
T
time-slots. Note
that each time-slot
t
can b e asso ciated with a static distance function
d
t
, whichis
assumed to b e distinct for each time-slot. Let
be the smallest value such that for
any edge
e
i
,
max
t
d
t
(
e
i
)
min
t
d
t
(
e
i
)
.We call
the
trac-load factor
.
A
dominating set
in a graph (digraph) is a subset
S
of vertices with the prop erty
that every vertex is either in
S
or is adjacent (has an edge) to some vertex in
S
.A
matching
M
in a graph is a subset of edges that do not share a vertex in common.
An
edge cover
S
in a graph is a subset of edges such that every vertex is incident
to at least one edge in
S
. A minimum-cost edge cover can be found in polynomial
time [22, pages 580{583].
1.2. Our Results
We study the basic
K
-center problem as well as several variations of this problem
under this model. We provide constant-factor approximation algorithms for all
these problems when there are two time-slots (this models the situation of \rush
hour" and \non-rush hour" travel times). For example, we could declare 7am to
9am and 4pm to 6pm as \rush hour" and all other times as \non-rush hour". (The
rush hour could happ en many times during the day. What is important is that
there are only two distinct distance functions to consider, one for rush hour and
one for non-rush hour.) We provide b est-possible approximation algorithms for
variants of the
K
-suppliers problem under this mo del.
We show that even under the simple time-slot model for varying distances, if there
are more than two time-slots then no constant approximation is p ossible. We also
provide approximation algorithms for several variations of the
K
-center problem
and the
K
-suppliers problem for arbitrarily many time-slots, including weights and
costs, with factors that are close to the best possible unless
P
=
NP
. These results
are summarized in Table 1. The only known lower b ound for anyofthe
K
-center
problems is 2, the lower b ound for the basic
K
-center problem. A lower b ound of
3 due to Karlo for the
K
-suppliers problem appears in [10]. It can be shown that
the
K
-center problem with weights and costs is a generalization of the
K
-suppliers
problem, which implies a lower bound of 3 for this problem. For two time-slots
with costs, all factors achieved in this pap er match the b est known factor for static
distance functions.
We can solve all of the ab ove problems in a unied manner using matching tech-
niques. The algorithms for arbitrary time-slots are based on an extension of the
Hochbaum-Shmoys metho d [9,10].
We also apply the matching approach to obtain a bicriteria approximation for the
asymmetric
K
-center problem, in which
G
is a directed graph. For this problem
d
t
(
u; v
)=
d
t
(
v; u
)may not hold. We give an algorithm that, for any nonnegative
integer
, uses at most
K
1+
3
+1
centers and covers all no des within distance
c
log
n
+
times the optimal distance, where
c
is the constant from the set cover
phase of the algorithm in [23]. The b est known algorithm for the asymmetric