ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. A Dantzig figure is a triple (P,x,y) in which P is a simple d -polytope with precisely 2d facets, x and y are vertices of P , and each facet is incident to x or y but not both. The famous d -step conjecture of linear programming is equivalent to the claim that always # d P(x,y) ≥ 1 , where # d P(x,y) denotes the number of paths that connect x to y by using precisely d edges of P . The recently formulated strong d -step conjecture makes a still stronger claim—namely, that always # d P(x,y) ≥ 2 d-1 . It is shown here that the strong d -step conjecture holds for d ≤ 4 , but fails for d ≥ 5 .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009334
Permalink