Approximation Schemes for Capacitated Geometric Network Design
Venue
ICALP 2011, Rynek Główny 12 (to appear)
Publication Year
2011
Authors
Anna Adamaszek, Artur Czumaj, Andrzej Lingas, Jakub Onufry Wojtaszczyk
BibTeX
Abstract
We study a capacitated network design problem in geometric setting. We assume that
the input consists of an integral link capacity k and two sets of points on a
plane, sources and sinks, each source/sink having an associated integral demand
(amount of flow to be shipped from/to). The capacitated geometric network design
problem is to construct a minimum-length network N that allows to route the
requested flow from sources to sinks, such that each link in N has capacity k; the
flow is splittable and parallel links are allowed in N. The capacitated geometric
network design problem generalizes, among others, the geometric Steiner tree
problem, and as such it is NP-hard. We show that if the demands are polynomially
bounded and the link capacity k is not too large, the single-sink capacitated
geometric network design problem admits a polynomial-time approximation scheme. If
the capacity is arbitrarily large, then we design a quasi-polynomial time
approximation scheme for the capacitated geometric network design problem allowing
for arbitrary number of sinks. Our results rely on a derivation of an upper bound
on the number of vertices different from sources and sinks (the so called Steiner
vertices) in an optimal network. The bound is polynomial in the total demand of the
sources.
