A new bound for the ratio between the 2-matching problem and its linear programming relaxation

A new bound for the ratio between the 2-matching problem and its linear programming relaxation

0.00 Avg rating0 Votes
Article ID: iaor20003805
Country: Germany
Volume: 86
Issue: 3
Start Page Number: 499
End Page Number: 514
Publication Date: Jan 1999
Journal: Mathematical Programming
Authors: ,
Keywords: programming: linear
Abstract:

Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem.

Reviews

Required fields are marked *. Your email address will not be published.