Approximating airports and railways

DOI10.4230/LIPICS.STACS.2018.5MaRDI QIDQ3304099zbMATH OpenOpenAlexFDO

Authors Anna Adamaszek, Antonios Foivos Antoniadis, Amit Kumar, Tobias Mömke

Publication date 5 August 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2018.5

zbMATH Keywords

approximation algorithmsfacility locationmetricnetwork designEuclidean spacePTAS

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• Airports and railways: facility location meets network design
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation algorithms for a facility location problem with service capacities
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Automata, Languages and Programming

Cites work

• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Airports and railways: facility location meets network design
• Approximation Algorithms for Problems Combining Facility Location and Network Design
• Approximation algorithms for a facility location problem with service capacities
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Approximation schemes for capacitated geometric network design
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Network flows. Theory, algorithms, and applications.
• New approximation algorithms for the unsplittable capacitated facility location problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

Cited in

(3)

• Airports and railways: facility location meets network design
• Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
• Airports and railways with unsplittable demand

This page was built for publication: Approximating airports and railways

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304099)