The Hirsch conjecture for the fractional stable set polytope

DOI10.1007/S10107-013-0723-3MaRDI QIDQ463733zbMATH OpenOpenAlexWikidataFDO

Authors Carla Michini, Antonio Sassano

Publication date 17 October 2014

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL http://doc.rero.ch/record/325706/files/10107_2013_Article_723.pdf

zbMATH Keywords

diameterpolytopestable set problem

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Extreme-point and pivoting methods (90C49) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• Upper bounds for the diameter and height of graphs of convex polyhedra
• scientific article; zbMATH DE number 16720
• The Hirsch conjecture is true for (0,1)-polytopes
• On the circuit diameter of some combinatorial polytopes

Cites work

• A counterexample to the Hirsch conjecture
• A linear bound on the diameter of the transportation polytope
• An Efficient Primal Simplex Algorithm for Maximum Weighted Vertex Packing on Bipartite Graphs
• How tight is the corner relaxation? Insights gained from the stable set problem
• scientific article; zbMATH DE number 1240224 (Why is no real title available?)
• scientific article; zbMATH DE number 3333883 (Why is no real title available?)
• scientific article; zbMATH DE number 3361920 (Why is no real title available?)
• On the Assignment Polytope
• On the facial structure of set packing polyhedra
• Signature classes of transportation polytopes
• Stable sets, corner polyhedra and the Chvàtal closure
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The Hirsch Conjecture for Dual Transportation Polyhedra
• The Hirsch conjecture is true for (0,1)-polytopes
• Vertex packings: Structural properties and algorithms

Cited in

(6)

• On the circuit diameter of some combinatorial polytopes
• Fractionally log-concave and sector-stable polynomials: counting planar matchings and more
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
• An efficient algorithm for vertex enumeration of arrangement
• Asymptotic bounds on the combinatorial diameter of random polytopes
• Vertex adjacencies in the set covering polyhedron

This page was built for publication: The Hirsch conjecture for the fractional stable set polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463733)