Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However asking for counter examples here might be a reasonable extended formulations problem.


Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first revisions, second revisions, new counter-examples, further revisions, further counter-examples, and so on.

  • It would be much better, if the authors were able to provide a mathematical proof that the given LP formulation indeed yields a full description of the TSP.

  • From the scientific point of view, it is certainly not enough to just state an LP formulation and to claim that it is correct, as long as nobody is able to explicitly construct a counter-example.

All in all, I would say that it is safe to ignore this paper as long as the authors do not provide supporting arguments for their claims.

  • 6
    $\begingroup$ And here is a book to ignore as well: worldscientific.com/worldscibooks/10.1142/9725 $\endgroup$ – Kristoffer Arnsfelt Hansen Dec 6 '18 at 10:15
  • 7
    $\begingroup$ The real question for me is, how does one get a named chair in OR at a major university..scratch that, how does one get a PhD in a mathematical discipline, while apparently not understanding linear algebra: arxiv.org/abs/1605.03243 $\endgroup$ – Sasho Nikolov Dec 8 '18 at 20:18
  • 6
    $\begingroup$ To clarify my comment: the paper I link to is coauthored by the authors of the paper in the question. They claim to have an example invalidating a certain definition of an extended formulation. They don't seem to realize that 1) the counterexample goes away once you apply a rotation/change of basis. 2) By elementary linear algebra, a change of basis shows that the equivalence of the definition they don't like to the one they do like. My mind is blown by the existence of papers like this. $\endgroup$ – Sasho Nikolov Dec 8 '18 at 22:38
  • $\begingroup$ @SashoNikolov I wish I knew more about EF. $\endgroup$ – Brout Dec 9 '18 at 3:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.