An improved approximation guarantee for prize-collecting TSP

Cites Work

The prize collecting traveling salesman problem
Title not available (Why is that?)
A General Approximation Technique for Constrained Forest Problems
A Reduction Method for Edge-Connectivity in Graphs
Worst-case analysis of a new heuristic for the travelling salesman problem
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
A note on the prize collecting traveling salesman problem
Title not available (Why is that?)
Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
Saving an epsilon
Heuristic analysis, linear programming and branch and bound
On a theorem of Mader
Approximation Algorithms for Orienteering and Discounted-Reward TSP
Pipage rounding: a new method of constructing algorithms with proven performance guarantee
The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
On some connectivity properties of Eulerian graphs
Improved algorithms for orienteering and related problems
Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
Title not available (Why is that?)
New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem
Survivable networks, linear programming relaxations and the parsimonious property
On the Integrality Gap of the Prize-Collecting Steiner Forest LP
Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems
An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem
A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
Pipage Rounding, Pessimistic Estimators and Matrix Concentration
An improved approximation algorithm for TSP in the half integral case
A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics

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)