Approximation Schemes for Capacitated Geometric Network Design

DOI10.1007/978-3-642-22006-7_3zbMath1332.68282OpenAlexW1862335956WikidataQ58203688 ScholiaQ58203688MaRDI QIDQ3012789

Anna Adamaszek, Jakub Onufry Wojtaszczyk, Andrzej Lingas, Artur Czumaj

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_3

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Approximating Airports and Railways

Cites Work

• Unnamed Item
• Unnamed Item
• The Steiner tree problem
• Approximation algorithms for a capacitated network design problem
• Approximating the Single-Sink Link-Installation Problem in Network Design
• A catalog of Hanan grid problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Approximation Algorithms for Buy-at-Bulk Geometric Network Design
• Bounds and Heuristics for Capacitated Routing Problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Approximation to the Minimum Cost Edge Installation Problem