Applications of cut polyhedra. II

DOI10.1016/0377-0427(94)90021-3zbMath0826.52013OpenAlexW4206054519MaRDI QIDQ1891020

Monique Laurent, Michel Marie Deza

Publication date: 5 July 1995

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-0427(94)90021-3

zbMATH Keywords

combinatorial optimizationmax-cut problemcut polyhedraBoole problem

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Gale and other diagrams (52B35)

Related Items

BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints, Mathematical Programming Models and Exact Algorithms, Application of cut polyhedra. I, New classes of facets of the cut polytope and tightness of \(I_{mm22}\) Bell inequalities, Improved compact formulations for metric and cut polyhedra, Algebraic and numerical techniques for the computation of matrix determinants, Clin d'oeil on \(L_1\)-embeddable planar graphs, A connection between positive semidefinite and Euclidean distance matrix completion problems, Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B, Classes of cut ideals and their Betti numbers, Cycle algebras and polytopes of matroids, Maximum Cut Parameterized by Crossing Number, Seminormality, canonical modules, and regularity of cut polytopes, Generating facets for the cut polytope of a graph by triangular elimination, Penalized semidefinite programming for quadratically-constrained quadratic optimization, A study of the performance of classical minimizers in the quantum approximate optimization algorithm, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, The coherency index, \(\ell_ 1\)-rigid graphs, A dynamic inequality generation scheme for polynomial programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Half-integral five-terminus flows
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Une propriété extremale des plans projectifs finis dans une classe de codes équidistants
• Combinatorial approaches to multiflow problems
• The classification of finite connected hypermetric spaces
• Polyhedra related to undirected multicommodity flows
• Experiments in quadratic 0-1 programming
• Matroids and multicommodity flows
• Weakly bipartite graphs and the max-cut problem
• Correlation polytopes: Their geometry and complexity
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Quantum probability - quantum logic
• A cone of inhomogeneous second-order polynomials
• Compositions in the bipartite subgraph polytope
• How far apart can the group multiplication tables be?
• Geometric algorithms and combinatorial optimization
• Bounds for equidistant codes and partial projective planes
• Bonferroni inequalities
• The hypermetric cone is polyhedral
• Laplacian eigenvalues and the maximum cut problem
• A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
• Sums of cuts and bipartite metrics
• L-polytopes and equiangular lines
• Application of cut polyhedra. I
• Hierarchical clustering schemes
• A generalized cut-condition for multiflows in matroids
• Equiangular lines
• On a certain distance of sets and the corresponding distance of functions
• Metrics and undirected cuts
• Generalized Radon Transform and Lévy’s Brownian Motion, II
• The Empty Sphere
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Closed Form Two-Sided Bounds for Probabilities that At Least r and Exactly r Out of n Events Occur
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Best Linear Bonferroni Bounds
• HYPERMETRIC GRAPHS
• On the cut polytope
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Mass transhipment problems and ideal metrics
• An Inequality for Probabilities
• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• On the Probability of the Occurrence of at Least $m$ Events Among $n$ Arbitrary Events
• Quantum Theory of Many-Particle Systems. I. Physical Interpretations by Means of Density Matrices, Natural Spin-Orbitals, and Convergence Problems in the Method of Configurational Interaction