Approximation algorithms for the generalized point-to-point problem

DOI10.4230/LIPICS.WADS.2025.28MaRDI QIDQ7312577zbMATH OpenFDO

Authors Zachary Friggstad, Mohammad Salavatipour, Hao Sun

Publication date 11 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.WADS.2025.28

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Cites work

• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• A General Approximation Technique for Constrained Forest Problems
• A tight bound on approximating arbitrary metrics by tree metrics
• Bypassing the embedding
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• On fixed cost k-flow problems
• On network design problems: fixed cost flows and the covering Steiner problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Revisiting Garg's 2-approximation algorithm for the \(k\)-MST problem in graphs
• Saving an epsilon: a 2-approximation for the k-MST problem in graphs
• Some APX-completeness results for cubic graphs
• The minimum shift design problem

This page was built for publication: Approximation algorithms for the generalized point-to-point problem

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