Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time

From: "Radosław Hofman" <radekh@xxxxxxxxx>
Date: Mon, 30 Oct 2006 14:48:54 +0100

Hi,

I have done some extra effort and gained Yannakakis, M., "Expressing
Combinatorial Optimization Problems by Linear Programs," Journal of Computer
and System Sciences 43 (1991) pp. 441-466, mentioned in your article.
Author of this is VERY strict that polytope cannot have less then
exponential number of vertexes - he even proves it in theorem 1.

Even more - his model of succinct representation can be used ONLY for 0/1
variable values, what is very clear on page 459, and has to be exponentially
large if not...

This of course makes your method incapable for large instances...

Cheers,

Radek Hofman

.

References:
- Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: Radosław Hofman
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: moustapha . diaby
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: Radoslaw Hofman
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: moustapha . diaby
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: tchow
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: moustapha . diaby
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: Radoslaw Hofman
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: moustapha . diaby
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: moustapha . diaby
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: Radoslaw Hofman
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: moustapha . diaby
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: Radoslaw Hofman
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: moustapha . diaby
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
  - From: Radoslaw Hofman

Prev by Date: an optimization problem
Next by Date: Re: Finding edges of a given polyhedra in 3D
Previous by thread: Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
Next by thread: Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
Index(es):
- Date
- Thread