Open Problem Garden

Continous analogue of Hirsch conjecture ★★

Author(s): Deza; Terlaky; Zinchenko

Conjecture   The order of the largest total curvature of the primal central path over all polytopes defined by inequalities in dimension is .

Keywords: curvature; polytope

Average diameter of a bounded cell of a simple arrangement ★★

Author(s): Deza; Terlaky; Zinchenko

Conjecture   The average diameter of a bounded cell of a simple arrangement defined by hyperplanes in dimension is not greater than .

Keywords: arrangement; diameter; polytope

Deza, Antoine

Terlaky, Tamas

Zinchenko, Yuriy

arrangement

Hamiltonian cycle

Savage, Carla

Matchings extend to Hamiltonian cycles in hypercubes ★★

Author(s): Ruskey; Savage

Keywords: Hamiltonian cycle; hypercube; matching

Ruskey, Frank