PaperlayerView exact revision on arXiv

Source-linked AI summary

New Inapproximability Bounds for TSP

Marek Karpinski, Michael Lampis, Richard Schmied

arXiv:1303.6437v2cs.CCcs.DMcs.DSmath.COmath.OC

TL;DR

Metric TSP and ATSP have known but small inapproximability bounds, while their algorithmic approximability remains a major open problem. This paper gives modular reductions through bounded-occurrence CSPs, using a new wheel-amplifier construction. It proves stronger hardness bounds for both problems, including the first ATSP improvement in more than a decade.

  • Problem

    Known hardness bounds were 185/184 for symmetric TSP and 117/116 for ATSP, leaving the approximability of these fundamental problems an open question.

    Source: §1 · pp. 1–2

  • Method

    The proof reduces MAX-E3-LIN2 to a specially structured bounded-occurrence CSP using a new wheel-amplifier variant, then reduces that CSP to TSP and ATSP.

    Source: §1 · p. 3

  • Results

    75/74 for ATSP and 123/122 for TSP are the new inapproximability bounds, respectively.

    Source: Assignment for Contact Variables · pp. 16, 21

  • Takeaways & Limitations

    The ATSP bound is the first improvement in more than a decade, while a constant-factor approximation for ATSP remains an open question.

    Source: §1 · p. 2, §7 · p. 21

    The tour construction assumes all two-variable equations in the Hybrid instance are satisfied and first analyzes tours that traverse forced edges only once.

    Source: §5.2 · p. 11, Assignment for Checker Variables · p. 14

Abstract

from arXiv · show

In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.

1 Introduction

The paper improves known inapproximability bounds for metric TSP and ATSP through modular reductions using bounded-occurrence CSPs and a new wheel-amplifier construction. Its reductions yield bounds of 123/122 for TSP and 75/74 for ATSP, the first ATSP improvement in more than a decade.

1 Introduction

  • The paper frames the new hardness bounds against a substantial gap from known algorithms, including the ATSP's O(log n/ log log n) approximation ratio.Christofides' 3/2 algorithm remains the best known efficient approximation for symmetric TSP, while Graphic TSP has improved to 7/5.Source: §1 · p. 1
  • 123/122 for TSP and 75/74 for ATSP improve the previous bounds of 185/184 and 117/116, respectively.The ATSP bound is the first improvement over Papadimitriou and Vempala's bound in more than a decade.Source: §1 · pp. 1–2
  • The new amplifier's special CSP structure permits constraints to be simulated essentially for free, helping make the reductions more economical.The approach is modular, passing through an intermediate bounded-occurrence CSP, and differs from the one-step reduction in.Source: §1 · pp. 2–3
  • The proof first reduces MAX-E3-LIN2 to a specially structured CSP with variables appearing exactly three times, using a new wheel-amplifier variant.The starting MAX-E3-LIN2 problem has equations over mod 2 with exactly three variables per equation.Source: §1 · p. 3
  • The second reduction maps the 3-regular CSP to TSP and ATSP, constructing gadgets for roughly one third of its constraints and simulating the rest without additional cost.The reductions use different gadgets for the two problems and exploit consistency properties of the gadgets.Source: §1 · p. 3

2 Preliminaries

The preliminaries formulate ATSP tours as connected, balanced spanning multisets of edges and specify the corresponding cost for disconnected quasi-tours. They also identify metric TSP as the undirected special case of ATSP.

2 Preliminaries

  • For directed edge multisets, a vertex's balance is its indegree minus its outdegree, and a directed graph is Eulerian exactly when it is connected and all vertices are balanced.In the undirected case, balance records whether the number of incident edges is odd or even.Source: §2 · pp. 3–4
  • A quasi-tour is a spanning edge multiset that balances every vertex; it is a tour when its edges form one connected component.Its cost is the sum of edge costs plus 2(con_T − 1), where con_T counts connected components.Source: §2 · p. 4
  • ATSP can equivalently be expressed as finding a minimum-cost tour: a connected spanning multiset of edges that balances all vertices.The usual formulation minimizes the length of a vertex ordering with shortest-path distances between consecutive vertices and back to the start.Source: §2 · p. 4
  • Metric TSP is the special case of ATSP whose instances are undirected graphs with positive edge weights.Source: §2 · p. 4

3 Bi-Wheel Amplifiers

The section introduces bi-wheel amplifiers, a variation on wheel amplifiers used to prove hardness for specially structured bounded-occurrence CSPs. It establishes their 3-regular amplification property with high probability and outlines a probabilistic argument for that result.

3 Bi-Wheel Amplifiers

  • A bi-wheel uses two disjoint cycles, with every seventh vertex a contact, and a random perfect matching between the checker vertices of the two cycles.This is a variation on the wheel amplifier, which uses one cycle and a random matching among its checker vertices.Source: §3 · pp. 4–5
  • The amplifier replaces a frequently appearing CSP variable with 3-occurrence variables linked by constraints so that an optimal assignment makes the new variables agree.For the wheel example, a variable appearing 2n times is replaced by 14n variables, one per wheel vertex.Source: §3 · pp. 4–5
  • In the CSP construction, cycle edges encode equality constraints and matching edges encode inequality constraints, with cycle equalities represented for free through consistency of the inequality gadgets.Contacts on the two cycles represent positive and negative appearances of the original variable.Source: §3 · p. 5
  • With high probability, bi-wheels are 3-regular amplifiers.Amplifiers have contact vertices of degree Δ−1, other vertices of degree Δ, and cuts large relative to the contacts on either side.Source: §3 · pp. 4–5
  • The proof adapts the wheel-amplifier analysis by bounding the probability that a vertex set is a minimal bad set, then applying a union bound.A comparison with a matching restricted to opposite checker halves reduces the bi-wheel analysis to the standard wheel argument; the graphs differ by rewiring two edges.Source: §3 · pp. 5–6
  • For balanced checker sets, the restricted-matching cut probability is roughly the standard-wheel probability up to polynomial factors, negligible against exponentially small probabilities.For unbalanced sets, the analysis bounds the probability by showing its maximum occurs at balance; minimal bad sets also satisfy c ≤ u/6.Source: §3 · pp. 6–7

4 Hybrid Problem

The section constructs a bounded-occurrence Hybrid CSP from MAX-E3LIN2 using a bi-wheel amplifier. Its 31m-equation instances preserve a strong satisfiability gap while making every variable occur exactly three times.

4 Hybrid Problem

  • Starting from Håstad’s bounded-occurrence MAX-E3LIN2 hardness, the authors define Hybrid as maximizing satisfied mod-2 equations with two or three variables.Source: §4 · pp. 7–8
  • 31m-equation Hybrid instances are NP-hard to distinguish at most εm unsatisfied from every assignment having at least (0.5−ε)m, with each variable occurring exactly three times.For any constant ε>0 and b∈{0,1}, they contain 21m x⊕y=0 equations, 9m x⊕y=1 equations, and m equations x⊕y⊕z=b.Source: §4 · p. 8
  • Each source-variable occurrence is redirected to a bi-wheel contact variable, whose matching and cycle equations allow assignments to be made consistent without decreasing satisfied equations.Source: §4 · pp. 8–9

5 TSP

This section proves metric TSP is NP-hard to approximate within any constant ratio below 123/122, using a gadget reduction from Hybrid. It analyzes the assignment-to-tour and tour-to-assignment directions through local costs and credits, completing the contact-variable assignment proof.

5 TSP

  • Metric TSP is NP-hard to approximate within any constant ratio less than 123/122.Source: §5 · p. 9

5.1 Construction

  • The reduction uses size-three equation and matching-edge gadgets, omits cycle-edge gadgets, and relies on consistent matching gadgets to encode those constraints.It also improves the size-three gadget and eliminates the variable part of the graph compared with.Source: §5 · p. 9

5.2 Tour from Assignment

  • An assignment leaving k of 31m Hybrid equations unsatisfied yields a tour costing at most 61m + 2ν + k + 2.Source: §5.2 · pp. 11–12

5.3 Assignment from Tour

  • A tour costing 61m + k − 2 yields a Hybrid assignment with at most k unsatisfied equations.The reverse proof assigns variables using forced and simple edges, then uses local-cost credits to account for unsatisfied equations.Source: §5.3 · pp. 12–13

Assignment for Checker Variables

Assignment for Contact Variables

  • Contact gadgets have a local-cost floor of 15.5; an honest assignment that violates the size-three equation requires cost at least 16.5, earning credit 1.Source: Assignment for Contact Variables · pp. 14–15
  • The assignment proof concludes that total credits are at most k and suffice to cover every equation left unsatisfied by the assignment.The conclusion follows by bounding the partition’s total local cost by 61m + k and expressing it as 61m plus the sum of credits.Source: Assignment for Contact Variables · p. 16
  • 123/122 is approached by a reduction that makes it NP-hard to distinguish tours of cost at most 61m′ + (δ+ε)m′ from tours costing at least 61.5m′ − (δ+ε)m′.Repeating each MAX-E3LIN2 equation ensures 2(ν + 1)/m′ ≤ δ; suitable choices of δ and ε make the ratio arbitrarily close to 123/122.Source: Assignment for Contact Variables · p. 16

6 ATSP

The ATSP reduction translates a bounded-occurrence Hybrid instance into a directed graph, with tours encoding assignments and their costs tracking unsatisfied equations. The proof establishes the 75/74 inapproximability threshold by showing both how assignments yield tours and how tours yield assignments.

6.1 Construction

  • Bidirected forced paths represent edges, while traversal direction in two cycles encodes truth assignments.The construction uses forced paths with edge weights w/L and builds a second cycle that uses matching edges in the opposite direction.Source: §6.1 · pp. 16–17
  • Three-variable equations are represented by a gadget connected to a central vertex using forced edges of weight λ.The equation gadget is a variant of the gadget used by Papadimitriou and Vempala.Source: §6.1 · pp. 17–18

6.2 Assignment to Tour

  • 37m + 5ν + 2mλ + 2νλ + k bounds the tour cost for an assignment leaving k equations unsatisfied.Here ν is the number of bi-wheels and m the number of equations in the Hybrid instance.Source: §6.2 · p. 18

6.3 Tour to Assignment

  • 37m + k + 2λm bounds a tour from which an assignment can be recovered with at most k unsatisfied equations.The proof uses extra local tour cost as credit to account for possible unsatisfied equations.Source: §6.3 · p. 19

Assignment for Checker Variables

  • Checker assignments are derived from whether simple edges enter and leave paired checker variables, with local tour cost supplying credit for violations.For an honest pair assigned 1, the forced edge must be used twice, giving local cost at least 6 and credit 3.Source: Assignment for Checker Variables · pp. 19–20

Assignment for Contact Variables

  • For contact variables, traversing a forced edge in both directions incurs extra local cost that can cover dishonest variables and unsatisfied equations.The proof concludes that all unsatisfied equations are paid for by credit induced by the tour.Source: Assignment for Contact Variables · p. 20

6 ATSP

  • The reduction establishes NP-hardness of approximating the asymmetric traveling salesperson problem (ATSP) within every constant approximation ratio strictly less than 75/74.The ratio between the two tour-cost cases can get arbitrarily close to 75/74 with appropriate choices of ε, δ, and λ.Source: §6 · p. 16, Assignment for Contact Variables · p. 21

7 Concluding Remarks

The paper establishes inapproximability thresholds of 75/74 for ATSP and 123/122 for TSP. It notes a substantial gap between the ATSP lower and upper bounds and identifies bi-wheel amplifiers as a possible tool for other problems.

7 Concluding Remarks

  • 75/74 for ATSP and 123/122 for TSP are the paper's inapproximability thresholds.Source: §7 · p. 21
  • ATSP's O(log n/ log log n) upper bound remains far from its 75/74 lower bound, leaving open whether an efficient constant-factor approximation exists.Source: §7 · p. 21
  • The authors identify bi-wheel amplifiers as a possible route to improved hardness results for problems such as Steiner Tree.Source: §7 · p. 21

Related papers

Loading 1303.6437v2…