How tight is the corner relaxation? Insights gained from the stable set problem
From MaRDI portal
Publication:448970
DOI10.1016/j.disopt.2012.02.004zbMath1252.90052OpenAlexW2139431443MaRDI QIDQ448970
Giacomo Nannicini, Carla Michini, Cornuéjols, Gérard
Publication date: 11 September 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2012.02.004
Related Items
Theoretical challenges towards cutting-plane selection, The Hirsch conjecture for the fractional stable set polytope, Can Cut-Generating Functions Be Good and Efficient?, On the Circuit Diameter of Some Combinatorial Polytopes, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, On the complexity of surrogate and group relaxation for integer linear programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A heuristic to generate rank-1 GMI cuts
- Chvátal closures for mixed integer programming problems
- How tight is the corner relaxation?
- Stable sets, corner polyhedra and the Chvàtal closure
- Random near-regular graphs and the node packing problem
- An exact threshold theorem for random graphs and the node-packing problem
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- Some polyhedra related to combinatorial problems
- Vertex packings: Structural properties and algorithms
- Triangle Factors in Random Graphs
- On the facial structure of set packing polyhedra
- On the maximal number of independent circuits in a graph
