Improved approximation algorithms for prize-collecting Steiner tree and TSP

DOI10.1137/090771429zbMATH Open1223.68125OpenAlexW2123087902MaRDI QIDQ3020008FDOQ3020008

MohammadHossein Bateni, Howard Karloff, Aaron Archer, Mohammad T. 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

Recommendations

• Elementary approximation algorithms for prize collecting Steiner tree problems
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
• scientific article; zbMATH DE number 1445375
• scientific article; zbMATH DE number 6783450
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem

zbMATH Keywords

approximation algorithmsSteiner treetraveling salesmanprize-collecting

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (39)

• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems
• Serving rides of equal importance for time-limited dial-a-ride
• Variations of the prize‐collecting Steiner tree problem
• A 3/2-approximation algorithm for some minimum-cost graph problems
• Complexity and approximation for traveling salesman problems with profits
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• Title not available (Why is that?)
• A note on the prize collecting traveling salesman problem
• An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme
• An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties
• On the Integrality Gap of the Prize-Collecting Steiner Forest LP
• Robust optimization for routing problems on trees
• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
• The prize-collecting call control problem on weighted lines and rings
• Title not available (Why is that?)
• FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
• Approximation algorithms for group prize-collecting and location-routing problems
• Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio
• Solving Steiner trees: Recent advances, challenges, and perspectives
• An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
• The restricted Chinese postman problems with penalties
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Exact approaches for solving robust prize-collecting Steiner tree problems
• Prize-Collecting TSP with a Budget Constraint
• An improved approximation guarantee for prize-collecting TSP
• Maximizing the number of rides served for time-limited Dial-a-Ride*
• Approximating minimum-cost connected \(T\)-joins
• A simple rounding scheme for multistage optimization
• An improved algorithm for the Steiner tree problem with bounded edge-length
• LP-based algorithms for multistage minimization problems
• Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties
• A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
• A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems
• A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
• On the Exact Solution of Prize-Collecting Steiner Tree Problems
• Approximation algorithms for prize-collecting capacitated network design problems

This page was built for publication: Improved approximation algorithms for prize-collecting Steiner tree and TSP

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