Re: Is this proof right?

From: Alexander T. Hamming (ath77_at_aol.com)
Date: 10/28/04 

Date: 28 Oct 2004 10:11:10 -0700

fake.addr@gmail.com (SD) wrote in message news:<10cddc5b.0410241448.53b646c4@posting.google.com>...
> Casey Hawthorne <caseyhHAM@SCRAMistar.ca> wrote in message news:<junmn0tcci1sqc1685mlom5rftdpd1lrbk@4ax.com>...
> > I believe that for the TSP to be solved in polynomial time by linear
> > programming the cities must be on lattice points.
>
> From what I read in the paper it required $x_{i s j} \in \{ 0, 1 \} $
> which, from what I recall, means we are dealing with a integer
> programming problem. Therefore it is not an LP formulation for TSP.

No! he made an IP formulation of TSP. Then he relaxed the constraints
so 0<=x<=1, making it an LP problem. He claimed that the maximum
solution to the LP problem is always integer with $x_{i s j} \in \{ 0,
1 \} $. I want to know if this is a correct claim. If so and if the IP
formulation is correct, then NP=P.

Relevant Pages

  • Re: Need An Idea For Teaching VBA
    ... I have Walkenbach's Excel 2007 Power ... programming problem of some sort that could be used in the class. ... "VBA programming" is huge topic. ... that's the programming problem itself, or the teaching time, or both. ...
    (microsoft.public.excel.misc)
  • -- Question about cutting-stock problem
    ... programming formulation to a cutting-stock problem. ... "theory" underlying the column-generation method is inapplicable, ...
    (sci.math)
  • Re: Critical thinking puzzle
    ... that this seems to be a variant of a "standard" programming problem called the ... >course the macro found the solutions in less than 1 second (not counting ... >programming time) vs an hour or so that I spent doing it the "old fashioned" ...
    (microsoft.public.excel.misc)
  • Re: Theory of programming
    ... I think the Turing machine is a poor model of computation for ... > representation which is 'runnable' but that representation is very far ... can be handy as a way to think about programming in functional languages. ... tremendous useful insight into every programming problem, ...
    (comp.programming)
  • Re: Programming skills - growing from amateur to pro
    ... Jerry Stuckle of comp.lang.php make plain: ... on this or that programming problem. ... The problem with the internet is there are far more poor tutorials ...
    (comp.lang.php)