Publication Data
Approximation Schemes for Capacitated Geometric Network Design
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.
