Arie
Tamir (University of Tel Aviv,
Short Biography
Arie
Tamir received his B.Sc. in Mathematics and Physics in 1966, and his M.Sc. in
Mathematics in 1968, from the
Lecture to be presented in EWI 2007
Title
Algorithmic
Results on Facility location Problems on Networks
Abstract
In
this talk we survey algorithmic results, obtained mostly during the last decade,
on a variety of facility location problems defined on network metric spaces. (A
network metric space is represented by some underlying undirected graph, and
nonnegative edge lengths which induce the distance function through shortest
paths.)
Classical multi-facility location problems like the p-median, p-center, the
uncapacitated facility location (UFL), and median and center problems with
mutual communication, have been known to be NP-hard ("combinatorially
difficult" to solve), since the mid 70's and early 80's. Around the same
time the first polynomial time algorithms for these models on special networks
like trees, series-parallel graphs and even k-trees were presented. Since then a
lot of progress has been made in approximating the above models on general
networks, and improving the efficiency of polynomial algorithms for obtaining
exact solutions for the simpler networks.
The first approximation and inapproximability results appeared in 1985. They
involved the p-center problem. It was shown by Dryer and Frieze (1985) that the
simple greedy approach ensures a factor 2 approximation (100 per cent error).
Surprisingly, this bound is tight, i.e., obtaining a smaller error is already
NP-hard, even for networks induced by planar rectilinear configurations. For
more than a decade no similar results were known for other classical location
problems listed above, until computer scientists were extensively exposed to
location models. Shmoys, Tardos and Aardel (1997) and Charikar, Guha, Tardos and
Shmoys (2002), obtained the first constant-factor approximation algorithm for
the (metric) UFL and p-median problems respectively. A variety of techniques
have been used for the design and analysis of improved approximation algorithms
for these models and their capacitated versions. Surprisingly, it has been shown
that some natural heuristic algorithms, like local search approaches, which were
suggested almost 40 years ago, actually guarantee a constant factor error. (The
best factor known today, 3+ , for the p-median problem is achieved by a simple
local search scheme based on repeatedly exchanging a set of p-servers.) We will
survey the most recent results, including inapproximability results, for the
above models and their extensions to fault-tolerant and capacitated versions. We
will also cite recent approximation results involving the location of obnoxious
facilities (dispersion problems), where the goal is to maximize some monotone
function of the distances between the facilities.
Approximation results for the location models with mutual communication (nonhomogeneous
facilities) are still quite rare in the literature.
Turning to networks with simple topologies like path, tree, series-parallel, and
even k-tree, we note that most problems mentioned above become tractable, i.e.,
they are solvable in polynomial time, (Ageev, IPCO 1992). We cite interesting
recent results and developments for classical models and some of their important
extensions that we plan to discuss during the talk.
For the classical unweighted p-center model on path and tree networks, there is
already an optimal linear time algorithm by Frederickson (1991). For path
networks, when p, the number of servers (new facilities), is small with respect
to n, the number of customers (existing facilities), there is even a simple
sublinear O(p2 log2 n) algorithm by Megiddo and Tamir (1981). In both
algorithms, when restricted to paths, the customers, viewed as real points, are
assumed to be sorted. Recent results by Halman (2005) on general LP-type models,
prove that for fixed values of p, unweighted continuous and discrete p-center
problems on path networks, are solvable in (expected) linear time even when
customer locations are not presorted. (Note that even the discrete 2-center
problem is not trivially solvable in linear time.)
For the UFL problem on path and tree networks the best known results have been
the O(n) and the O(n2) algorithms in Hassin and Tamir (1991) and Gimadi (1983)
respectively. For trees, Shah (2002) used computational geometry techniques,
designed to maintain linear functions on trees efficiently, and derived an O(n
log n) algorithm for UFL and the min-coverage with penalties problems.
For the weighted p-median problem on path and tree networks the best known
results are the O(pn) and the O(pn2) algorithms in Hassin and Tamir (1991) and
Tamir (1996), respectively. Recently, extending the techniques of Shah (2002),
Benkoczi (2004), provided an improved O(n logp+2 n) subquadratic algorithm for a
fixed value of p 4. (The 1-, 2- and 3- median problems are solvable in O(n), O(n
log n) and O(n log3 n) times respectively.)
For the weighted p-coverage problem on path and tree networks the best known
results are the O(pn log n) and the O(pn2) algorithms in Van Hoesel and
Wagelmans (1991) and Tamir (1996), respectively. It is not yet known whether the
techniques of Shah (2002) and Benkoczi (2004) can be modified and applied to the
p-coverage problem on trees to yield subquadratic algorithms even for fixed
values of p.
Polynomial time algorithms for homogeneous p-facility location problems on path,
tree and other topologies for more general objective functions have been
reported in the literature over the last decade. We cite the polynomial
algorithms for the cent-dian and the k-centrum objectives in Tamir, Perez-Brito,
Moreno-Perez (1998), Tamir (2001), and Yu and Wang (2002). The polynomial
solvability of the more general multi facility convex ordered median problem
even on a path network remains unknown.
An improvement in the complexity of solving the (non-homogeneous) p-center
problem with mutual communication on tree networks was recently presented by
Averbakh and Berman (Networks 2002). It is based on a clever implementation of
the general parametric approach of Megiddo (1979, 1983). A further refinement in
Tamir (Networks 2004) has led to modified (subquadratic in n) bound of O(p3 (log
log p)(log p)+p(n+p)log2(n+p)). The discrete version can also be solved in O(p2n
log n log(n+p)) time, Tamir (Networks 2004).
The (non-homogeneous) p-median problem with mutual communication on tree
networks has been known to be solvable by a sequence of at most n-1 min-cut
problems on a general graph with O(p) vertices. Some improvements were presented
in Tamir (1993). No recent results have been reported since then.
The polynomial solvability of the min-coverage problem with mutual communication
on a tree network remains open. The min-coverage problem on a path is reducable
to a min-cut problem on some equivalent undirected graph, and therefore has a
polynomial time algorithm, Tamir (1994).
In view of the above solvability results, we should note that not all path and
tree location problems are efficiently solvable. There are several important
multi facility problems on path and tree networks that are strongly NP-hard.
Following are some interesting examples:
The p-center round trip problem defined on a star network with a 'large' set-up
cost at the central point of the star is equivalent to the vertex cover problem
on a general undirected graph, Kolen and Tamir (1990).
The p-median with mutual-communication problem with a 'large' set-up cost at the
central point of a star network with only 3 leaves is equivalent to the
3-terminal min-cut problem on a general undirected graph with O(p) vertices.
The p-anti median and the p-anti center with mutual communication dispersion
problems on a single edge topology are equivalent to the max-cut and
Hamiltonian-path problems on a general undirected graph with O(p) vertices.
Coverage of a set of existing facilities, real points, by placing a set of
movable rulers (intervals) of different lengths.
In the location problems listed above, customers (existing facilities) as well
as servers (new facilities) are all represented by points on the network metric
space. To capture more realistic and practical problems, more general models,
where facilities are represented by subgraphs, e.g., subpaths or subtrees, have
been introduced and studied in the literature. (See surveys on 'extensive'
facilities by Plastria (2002) and Diaz-Banez, Mesa, Schobel (2004).) We note
that even the location of a single subpath or subtree extensive facility on a
general network is already strongly NP-hard.
We will discuss in this talk most recent results on locating extensive
facilities on tree networks. Tamir, Puerto, Mesa, Rodriguez-Chia (J of
Algorithms 2005) consider the location of a subpath or a subtree single facility
optimizing optimizing the center and the median objectives, where customers are
modelled by the tree nodes. Subquadratic algorithms are presented for most of
these problems, and NP-hardness is established for the rest.
Puerto and Tamir (Math Prog 2005) prove submodularity properties for the problem
of locating a subtree facility with respect to the convex ordered median
objective, and use them, as well as other results on reducability into linear
programs, to design polynomial time algorithms for continuous and discrete
versions of the model.
Finally, we will discuss the results in Puerto, Tamir, Mesa, Perez-Brito (2005),
who study a tree network model where customers and servers are represented by
subtrees and points respectively. They focus on min-max center multifacility
problems and provide polynomial time algorithms for their solution. In
particular, they prove that the classical linear time algorithms of Handler from
1973, 1976 for the continuous unweighted 1- and 2- center problems, extend to
the 'extensive' subtree customer model without increasing the complexity.