Linear programming relaxations of \textsc{maxcut}
From MaRDI portal
Publication:2934582
Recommendations
- Stronger linear programming relaxations of max-cut
- Integrality gaps for Sherali-Adams relaxations
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
- Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
Cited in
(36)- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- Stronger linear programming relaxations of max-cut
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Lift \& project systems performing on the partial-vertex-cover polytope
- Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- On the linear relaxation of the \(s-t\)-cut problem with budget constraints
- Integrality gaps for colorful matchings
- Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
- Exponential lower bounds for polytopes in combinatorial optimization
- Convex relaxations and integrality gaps
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- Sherali-Adams relaxations for valued CSPs
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
- scientific article; zbMATH DE number 4068611 (Why is no real title available?)
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- Rank bounds for a hierarchy of Lovász and Schrijver
- scientific article; zbMATH DE number 7378399 (Why is no real title available?)
- Superlinear Integrality Gaps for the Minimum Majority Problem
- Sum-of-squares bounds via Boolean function analysis
- Sherali-adams strikes back
- Sherali-Adams strikes back
- Integrality gaps for Sherali-Adams relaxations
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- The power of Sherali-Adams relaxations for general-valued CSPs
- Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
- A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
- Instance-specific linear relaxations of semidefinite optimization problems
- Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT
- Uncapacitated flow-based extended formulations
This page was built for publication: Linear programming relaxations of \textsc{maxcut}
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934582)
