The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
Publication:1179735
DOI10.1007/BF02115753zbMath0741.90077OpenAlexW2003648292MaRDI QIDQ1179735
Publication date: 27 June 1992
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02115753
Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Quadratic programming (90C20) Boolean programming (90C09) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items (33)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The max-cut problem on graphs not contractible to \(K_ 5\)
- Facets of the clique partitioning polytope
- Upper-bounds for quadratic 0-1 maximization
- A solvable case of quadratic 0-1 programming
- On clustering problems with connected optima in Euclidean spaces
- A decomposition method for minimizing quadratic pseudo-Boolean functions
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- On cutting-plane proofs in combinatorial optimization
- Matroids and multicommodity flows
- The ellipsoid method and its consequences in combinatorial optimization
- Weakly bipartite graphs and the max-cut problem
- On the equivalence of paved-duality and standard linearization in nonlinear 0-1 optimization
- Compositions in the bipartite subgraph polytope
- On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
- Collapsing and lifting for the cut cone
- The cut polytope and the Boolean quadric polytope
- The basic algorithm for pseudo-Boolean programming revisited
- On the notion of balance of a signed graph
- Nonlinear 0–1 programming: I. Linearization techniques
- Metrics and undirected cuts
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Facets of the Bipartite Subgraph Polytope
- Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
- Roof duality for polynomial 0–1 optimization
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Methods of Nonlinear 0-1 Programming
- Vertices Belonging to All or to No Maximum Stable Sets of a Graph
- Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
- Boolean and Graph Theoretic Formulations of the Simple Plant Location Problem
- Clique-Web Facets for Multicut Polytopes
- Pseudo-Boolean Solutions to Multidimensional Location Problems
- Polynomially Complete Fault Detection Problems
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- A Cut Approach to the Rectilinear Distance Facility Location Problem
- Optimal Test Generation in Combinational Networks by Pseudo-Boolean Programming
- Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
- On the cut polytope
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
- Maximum likelihood paired comparison ranking by linear programming
- Quadratic Binary Programming with Application to Capital-Budgeting Problems
- A Selection Problem of Shared Fixed Costs and Network Flows
- Notes—On a Selection Problem
This page was built for publication: The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds