Re: Is this proof right?

From: Casey Hawthorne (caseyhHAM_at_SCRAMistar.ca)
Date: 10/24/04 

Date: Sun, 24 Oct 2004 07:56:40 GMT

I believe that for the TSP to be solved in polynomial time by linear
programming the cities must be on lattice points.

There might be other constraints.

ath77@aol.com (Alexander T. Hamming) wrote:

>I found this.
>
>http://www.business.uconn.edu/users/mdiaby/tsplp/
>
>Does anyone know if its right?
>
>ATH 

--
Regards,
Casey

Relevant Pages

  • Re: Is this proof right?
    ... > I believe that for the TSP to be solved in polynomial time by linear ... > programming the cities must be on lattice points. ...
    (comp.theory)
  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... > cities, ... > constraints still dominates the number of possible paths. ... between Problem IP and Problem IP-bar in my paper is that *extreme ... polytope compared to the number of paths. ...
    (comp.theory)
  • Re: POD speed
    ... I listed reasons that enforcement of database ... constraints in application code is error-prone compared to enforcement by the DBMS using ... implement outside the DBMS. ... > programming class I've seen as one ...
    (comp.lang.java.databases)
  • Re: Need help with reordering items
    ... CREATE TABLE Cities ... INSERT INTO Cities VALUES ('New York', ... Please post DDL, so that people do not have to guess what the keys, ... constraints, Declarative Referential Integrity, datatypes, etc. in your ...
    (microsoft.public.sqlserver.programming)
  • Re: Philosphy of programming
    ... there are certain constraints on the model. ... on simulation and the ... It's the constraints on the simulation that make programming ... reality, and then creating a simulation of that limitted reality which can ...
    (comp.programming)