An improved approximation guarantee for prize-collecting TSP

Cites work

scientific article; zbMATH DE number 1305468 (Why is no real title available?)
scientific article; zbMATH DE number 1507215 (Why is no real title available?)
scientific article; zbMATH DE number 6783450 (Why is no real title available?)
A General Approximation Technique for Constrained Forest Problems
A Reduction Method for Edge-Connectivity in Graphs
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
A note on the prize collecting traveling salesman problem
A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
A unified PTAS for prize collecting TSP and Steiner tree problem in doubling metrics
An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
An improved approximation algorithm for TSP in the half integral case
Approximation Algorithms for Orienteering and Discounted-Reward TSP
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems
Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
Heuristic analysis, linear programming and branch and bound
Improved algorithms for orienteering and related problems
Improved approximation algorithms for prize-collecting Steiner tree and TSP
Maximizing a monotone submodular function subject to a matroid constraint
New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem
On a theorem of Mader
On some connectivity properties of Eulerian graphs
On the integrality gap of the prize-collecting Steiner forest LP
Pipage rounding, pessimistic estimators and matrix concentration
Pipage rounding: a new method of constructing algorithms with proven performance guarantee
Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
Survivable networks, linear programming relaxations and the parsimonious property
The prize collecting traveling salesman problem
The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
Worst-case analysis of a new heuristic for the travelling salesman problem

This page was built for publication: An improved approximation guarantee for prize-collecting TSP

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