Re: Hofman and Diaby talk about P=NP at INFORMS 2007



On Feb 13, 10:37 am, t...@xxxxxxxxxxxxx wrote:
In article <1171376630.989060.181...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<moustapha.di...@xxxxxxxxxxxxxxxxxx> wrote:
There is no *mathematical* connection between the polytope of my model
and the TSP polytope. Proposition 1 in my paper shows equivalence of
the feasible set of my model and the assignment polytope. You get a
TSP solution out of it only by interpretation. ...The connection to a
TSP solution is only cognitive (The mathematical connection is to the
assignment polytope as proved in Proposition 1.).

Of course you didn't build your model with what you call a "mathematical"
correspondence to the TSP polytope in mind, and the connection remains
only "cognitive" in *your* mind. However, once your model has been
constructed, one can study it and derive further consequences from
its existence. This is what Moews has done, and he has shown that
from your model, one can derive a *mathematical* connection to the TSP
polytope---


And, which exact formulation of the the TSP polytope did he use to da
that again? ...You don't know what you are saying.

//MD

.



Relevant Pages

  • Re: Discussion regarding Mr. Diabys algorithm
    ... Polytope, since I am actually reformulating an Assignment Polytope! ... you stand comes from certain river and reached destination river using ... You can only check if % of water in certain channel comes from ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... "LP formulation has the structure of the Assignment Polytope". ... If we consider assignment polytope as such that has every row and column ... produces incorrect solutions... ... is equivalent to another NP-complete problem, so reformulation of TSP to 0-1 ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... atleast one optimal tour, within Polynomial time, by walking across the ... vertexes of your new Assignment Polytope that has Polynomial size. ... The feasible set of the LP relaxation ... solution for the CONVEX COMBINATION OF PATHS, ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... numbers such 20 is the convex combination of those numbers. ... I completlee agree that every TSP correspond to some BLP, ... TSP polytope), you try to see if you cannot express the same problem ... The Assignment polytope has been studied as much, if not more than, the ...
    (comp.theory)
  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... good to keep pointing to the arguments in your paper, ... Proposition 1 shows that *the* polytope of my IP maps ... exactly onto *the* assignment polytope. ... Bringing the TSP polytope into the picture was my mistake, ...
    (comp.theory)