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: a 2-approximation for the \(k\)-MST problem in graphs
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
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)