Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
From MaRDI portal
Publication:3020008
DOI10.1137/090771429zbMath1223.68125OpenAlexW2123087902MaRDI QIDQ3020008
MohammadHossein Bateni, Aaron Archer, Howard J. Karloff, Mohammad Taghi Hajiaghayi
Publication date: 29 July 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/090771429
Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (31)
An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties ⋮ Robust optimization for routing problems on trees ⋮ Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ On the Exact Solution of Prize-Collecting Steiner Tree Problems ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ The restricted Chinese postman problems with penalties ⋮ A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems ⋮ A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem ⋮ FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Approximation algorithms for prize-collecting capacitated network design problems ⋮ A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems ⋮ Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio ⋮ Unnamed Item ⋮ Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems ⋮ A primal-dual algorithm for the generalized prize-collecting Steiner forest problem ⋮ Complexity and approximation for traveling salesman problems with profits ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ A simple rounding scheme for multistage optimization ⋮ Prize-Collecting TSP with a Budget Constraint ⋮ A 3/2-approximation algorithm for some minimum-cost graph problems ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ A 2-approximation for the \(k\)-prize-collecting Steiner tree problem ⋮ Approximating minimum-cost connected \(T\)-joins ⋮ Exact approaches for solving robust prize-collecting Steiner tree problems ⋮ Serving rides of equal importance for time-limited dial-a-ride ⋮ LP-based algorithms for multistage minimization problems
This page was built for publication: Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
