Sublinear algorithms for TSP via path covers
From MaRDI portal
Cites work
- 8/7-approximation algorithm for (1,2)-TSP
- \(\frac {13}{9}\)-approximation for graphic TSP
- A (slightly) improved approximation algorithm for metric TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating Graphic TSP by Matchings
- Beating greedy matching in sublinear time
- Dynamic (1+ )-approximate matching size in truly sublinear update time
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Estimating the weight of metric minimum spanning trees in sublinear-time
- scientific article; zbMATH DE number 3746840 (Why is no real title available?)
- Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
- Local computation algorithms for maximum matching: new lower bounds
- New approximation algorithms for \((1,2)\)-TSP
- Reducibility among combinatorial problems
- Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
- Sublinear algorithms and lower bounds for estimating MST and TSP cost in general metrics
- Sublinear algorithms and lower bounds for metric TSP cost estimation
- Sublinear algorithms for (1.5+)-approximate matching
- Sublinear time algorithms and complexity of approximate maximum matching
- The Traveling Salesman Problem with Distances One and Two
- Time-optimal sublinear algorithms for matching and vertex cover
- Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.
This page was built for publication: Sublinear algorithms for TSP via path covers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875190)
