2007/01/03 by Moustapha Diaby, Diaby, Moustapha
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.cs/0701014
Using an approach that seems to be patterned after that of Yannakakis, Hofman argues that an NP-complete problem cannot be formulated as a polynomial bounded-sized linear programming problem. He then goes on to propose a "construct" that he claims to be a counter-example to recently published linear programming formulations of the Traveling Salesman Problem (TSP) and the Quadratic Assignment Problems (QAP), respectively. In this paper, we show that Hofman's construct is flawed, and provide further proof that his "counter-example" is invalid.