The Hirsch conjecture for the fractional stable set polytope

DOI10.1007/S10107-013-0723-3zbMATH Open1297.90086OpenAlexW1985422831WikidataQ123195740 ScholiaQ123195740MaRDI QIDQ463733FDOQ463733

Antonio Sassano, Carla Michini

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

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

zbMATH Keywords

diameterpolytopestable set problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• On the Circuit Diameter of Some Combinatorial Polytopes
• Fractionally log-concave and sector-stable polynomials: counting planar matchings and more
• Vertex adjacencies in the set covering polyhedron
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming

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)