5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
20
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 7
    $\begingroup$ And here is a book to ignore as well: worldscientific.com/worldscibooks/10.1142/9725 $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Dec 6, 2018 at 10:15
  • 8
    $\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, 2018 at 20:18
  • 7
    $\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, 2018 at 22:38
  • $\begingroup$ @SashoNikolov I wish I knew more about EF. $\endgroup$
    – Turbo
    Dec 9, 2018 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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