The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
From MaRDI portal
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
On characterization of maximal independent sets via quadratic optimization, \(f\)-flip strategies for unconstrained binary quadratic programming, Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem, Introduction to QUBO, Applications and Computational Advances for Solving the QUBO Model, Applications of cut polyhedra. II, On decomposability of multilinear sets, QUBO formulations of the longest path problem, Separator-based data reduction for signed graph balancing, Fast 1-flip neighborhood evaluations for large-scale pseudo-Boolean optimization using posiform representation, The unconstrained binary quadratic programming problem: a survey, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, On optimization problems in acyclic hypergraphs, A new penalty parameter for linearly constrained 0--1 quadratic programming problems, Partitioning planar graphs: a fast combinatorial approach for max-cut, A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, Binary positive semidefinite matrices and associated integer polytopes, A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), A multiple search operator heuristic for the max-k-cut problem, Berge-acyclic multilinear 0-1 optimization problems, The generalized vertex cover problem and some variations, Pseudo-Boolean optimization, Minimization of ordered, symmetric half-products, Global optimization of multilevel electricity market models including network design and graph partitioning, A tight lower bound for a special case of quadratic 0-1 programming, A filled function method for quadratic programs with binary constraints†, Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems, Quantum bridge analytics. I: A tutorial on formulating and using QUBO models, Quantum bridge analytics. I: A tutorial on formulating and using QUBO models, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, The line index and minimum cut of weighted graphs, The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
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
