# 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 ﬂow 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 ﬂow from sources to sinks, such that each link in N has capacity k; the
ﬂow 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.