How Many Steps?

Abstract

Due in considerable measure to its connection with linear programming, the combinatorial study of convex polytopes has progressed greatly in the past twenty-five years and many outstanding problems have been solved. However, the d-step conjecture, first formulated by W. M. Hirsch in 1957, remains unsettled. Both for its intrinsic interest and for its relationship to questions of computational complexity, it is probably the most important open problem on the combinatorial structure of polytopes. This report presents several equivalent forms of the d-step conjecture. Some deal explicitly with edge-paths on polytopes, one involves matrix pivot operations, and one concerns an exchange process for simplicial bases. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1980
Accession Number
ADA087860

Entities

People

  • Victor Klee

Organizations

  • University of Washington

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computer Programming
  • Diameters
  • Graph Theory
  • Heuristic Methods
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Military Research
  • New York
  • Operations Research
  • Simplex Method
  • Two Dimensional
  • Vector Spaces

Readers

  • Educational Psychology
  • Graph Algorithms and Convex Optimization.