Search: onr:"swepub:oai:lup.lub.lu.se:8b556297-c5a5-4bc2-afa2-7a0bdaa2e6c3" >
Approximation schem...
Approximation schemes for capacitated geometric network design
-
- Adamaszek, Anna (author)
- University of Copenhagen
-
- Czumaj, Artur (author)
- University of Warwick
-
- Lingas, Andrzej (author)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
show more...
-
- Wojtaszczyk, Jakub Onufry (author)
- Google Inc.
-
show less...
-
(creator_code:org_t)
- 2018
- 2018
- English 27 s.
-
In: SIAM Journal on Discrete Mathematics. - 0895-4801. ; 32:4, s. 2720-2746
- Related links:
-
http://dx.doi.org/10...
-
show more...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- We study a capacitated network design problem in a geometric setting. The input consists of an integral edge capacity k and two sets of points on the Euclidean plane, sources, and sinks, with an integral demand for each point. The demand of each source specifies the amount of flow that has to be shipped from the source, and the demand of each sink specifies the amount of flow that has to be shipped to the sink. The goal is to construct a minimum-length network that allows one to route the requested flow from the sources to the sinks and where each edge in the network has capacity k. The vertices of the network are not constrained to the sets of sinks and sources-any point on the Euclidean plane can be used as a vertex. The flow is splittable and parallel edges are allowed. 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 edge 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 an 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.
Subject headings
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Telekommunikation (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Telecommunications (hsv//eng)
Keyword
- Approximation schemes
- Geometric approximation
- Network design
Publication and Content Type
- art (subject category)
- ref (subject category)
Find in a library
To the university's database