<p>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.</p>

<ul>
<li><p>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. </p></li>
<li><p>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.</p></li>
</ul>

<p>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.</p>

CC BY-SA 4.0
2018-12-06T10:15:13.620Z
And here is a book to ignore as well: https://www.worldscientific.com/worldscibooks/10.1142/9725
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2018-12-08T20:18:44.390Z
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: https://arxiv.org/abs/1605.03243
Sasho Nikolov
CC BY-SA 4.0
2018-12-08T22:38:39.850Z
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.
Sasho Nikolov
CC BY-SA 4.0
2018-12-09T03:21:13.153Z
@SashoNikolov I wish I knew more about EF.
Turbo
CC BY-SA 4.0
2018-12-06T09:56:10.530Z
2018-12-06T09:56:10.530Z
Gamow
<p>Is there a counterexample to this claim <a href="https://arxiv.org/abs/1610.00353" rel="noreferrer">https://arxiv.org/abs/1610.00353</a>? They claim a <span class="math-container">$O(n^6)$</span> 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.</p>

<reference-request><linear-programming><p-vs-np><integer-programming><complexity>
Is there a counterexample to this work?
Turbo
# Is there a counterexample to this work?

(Asked by: username_0 on 2018-12-06)

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.

**Tags:** reference-request, linear-programming, p-vs-np, integer-programming, complexity


---

## 1 answers

### Answer by username_1 on 2018-12-06. Score: 20 | Accepted answer

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.

> **Comments:**
> **username_2**: And here is a book to ignore as well: https://www.worldscientific.com/worldscibooks/10.1142/9725  
> **username_3**: 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: https://arxiv.org/abs/1605.03243  
> **username_3**: 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.  
> **username_0**: @SashoNikolov I wish I knew more about EF.  

---

