Approximation Schemes for Capacitated Geometric Network Design

DOI10.1137/16M1108005zbMath1403.68339OpenAlexW2902760174MaRDI QIDQ4556954

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

Publication date: 28 November 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1108005

zbMATH Keywords

approximation schemesnetwork designgeometric approximation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• 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
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• Approximation to the Minimum Cost Edge Installation Problem

This page was built for publication: Approximation Schemes for Capacitated Geometric Network Design