Dual charging for half-integral TSP

DOI10.4230/LIPICS.APPROX/RANDOM.2025.21MaRDI QIDQ7346849zbMATH OpenFDO

Authors Nathan Klein, Mehrshad Taziki

Publication date 11 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2025.21

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• \(\frac {13}{9}\)-approximation for graphic TSP
• A (slightly) improved approximation algorithm for metric TSP
• A 1.5-approximation for path TSP
• A deterministic better-than-3/2 approximation algorithm for metric TSP
• A lower bound for the max entropy algorithm for TSP
• A Randomized Rounding Approach to the Traveling Salesman Problem
• 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
• Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications
• Capacity lower bounds via productization
• From trees to polynomials and back again: new capacity bounds with applications to TSP
• scientific article; zbMATH DE number 3746840 (Why is no real title available?)
• Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
• Lower bounds for contingency tables via Lorentzian polynomials
• Matching, Euler tours and the Chinese postman
• Negative dependence and the geometry of polynomials
• New inapproximability bounds for TSP
• On the Distribution of the Number of Successes in Independent Trials
• Optimizing over the subtour polytope of the travelling salesman problem
• Probabilistic bounds on the coefficients of polynomials with only real zeros
• Removing and adding edges for the traveling salesman problem
• Solution of a Large-Scale Traveling-Salesman Problem
• Survivable networks, linear programming relaxations and the parsimonious property
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Towards improving Christofides algorithm for half-integer TSP
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all

Cited in

(1)

• Maximum entropy is a 10/7-approximation algorithm for the TSP on half-integral cycle cut instances

This page was built for publication: Dual charging for half-integral TSP

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