Applications of cut polyhedra. II (Q1891020): Difference between revisions

In this second part of their article [ibid., 191-216 (1994; see above)] the authors develop further applications of cut polyhedra, such as the max-cut problem, the Boole problem, the multicommodity flow problems in combinatorial optimization, lattice holes in the geometry of numbers, and others.

0 references

zbMATH Keywords

cut polyhedra

0 references

max-cut problem

0 references

Boole problem

0 references

combinatorial optimization

0 references

reviewed by

Mihai Turinici

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0377-0427(94)90021-3

0 references

0 references

0 references

0 references

The cut cone,L1 embeddability, complexity, and multicommodity flows

0 references

A bound on the $k$-gonality of facets of the hypermetric cone and related complexity problems

0 references

The max-cut problem on graphs not contractible to $K_ 5$

0 references

An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design

0 references

Experiments in quadratic 0-1 programming

0 references

On the cut polytope

0 references

Q3069694

0 references

The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds

0 references

Closed Form Two-Sided Bounds for Probabilities that At Least r and Exactly r Out of n Events Occur

0 references

Q4105702

0 references

Q4723677

0 references

On the Probability of the Occurrence of at Least $m$ Events Among $n$ Arbitrary Events

0 references

An Inequality for Probabilities

0 references

Laplacian eigenvalues and the maximum cut problem

0 references

Une propriété extremale des plans projectifs finis dans une classe de codes équidistants

0 references

L-polytopes and equiangular lines

0 references

HYPERMETRIC GRAPHS

0 references

Q3137180

0 references

The hypermetric cone is polyhedral

0 references

Application of cut polyhedra. I

0 references

How far apart can the group multiplication tables be?

0 references

Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?

0 references

A cone of inhomogeneous second-order polynomials

0 references

The Empty Sphere

0 references

Compositions in the bipartite subgraph polytope

0 references

Q5514188

0 references

Bonferroni inequalities

0 references

Q4198056

0 references

Q4208509

0 references

Geometric algorithms and combinatorial optimization

0 references

Weakly bipartite graphs and the max-cut problem

0 references

Finding a Maximum Cut of a Planar Graph in Polynomial Time

0 references

Bounds for equidistant codes and partial projective planes

0 references

Q5629416

0 references

Hierarchical clustering schemes

0 references

Metrics and undirected cuts

0 references

Half-integral five-terminus flows

0 references

Sums of cuts and bipartite metrics

0 references

Best Linear Bonferroni Bounds

0 references

Q3274182

0 references

Equiangular lines

0 references

Q3856789

0 references

Combinatorial approaches to multiflow problems

0 references

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

0 references

On a certain distance of sets and the corresponding distance of functions

0 references

Generalized Radon Transform and Lévy’s Brownian Motion, II

0 references

Quantum probability - quantum logic

0 references

Correlation polytopes: Their geometry and complexity

0 references

Q3137209

0 references

Nonpolyhedral Relaxations of Graph-Bisection Problems

0 references

Mass transhipment problems and ideal metrics

0 references

Q3851094

0 references

Q3818127

0 references

A generalized cut-condition for multiflows in matroids

0 references

Matroids and multicommodity flows

0 references

The classification of finite connected hypermetric spaces

0 references

Q5847989

0 references

Identifiers

zbMATH Open document ID

0826.52013

0 references

DOI

10.1016/0377-0427(94)90021-3

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1891020

@@ Property / full work available at URL @@
+https://doi.org/10.1016/0377-0427(94)90021-3
+Normal rank
@@ Property / OpenAlex ID @@
+W4206054519
@@ Property / OpenAlex ID: W4206054519 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3954484
@@ Property / cites work: Q3954484 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3858801
@@ Property / cites work: Q3858801 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3310385
@@ Property / cites work: Q3310385 / rank @@
+Normal rank
@@ Property / cites work @@
+The cut cone,L1 embeddability, complexity, and multicommodity flows
+Normal rank
@@ Property / cites work @@
+A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
+Normal rank
@@ Property / cites work @@
+The max-cut problem on graphs not contractible to \(K_ 5\)
+Normal rank
@@ Property / cites work @@
+An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
+Normal rank
@@ Property / cites work @@
+Experiments in quadratic 0-1 programming
@@ Property / cites work: Experiments in quadratic 0-1 programming / rank @@
+Normal rank
@@ Property / cites work @@
+On the cut polytope
@@ Property / cites work: On the cut polytope / rank @@
+Normal rank
@@ Property / cites work @@
+Q3069694
@@ Property / cites work: Q3069694 / rank @@
+Normal rank
@@ Property / cites work @@
+The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
+Normal rank
@@ Property / cites work @@
+Closed Form Two-Sided Bounds for Probabilities that At Least <i>r</i> and Exactly <i>r</i> Out of <i>n</i> Events Occur
+Normal rank
@@ Property / cites work @@
+Q4105702
@@ Property / cites work: Q4105702 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4723677
@@ Property / cites work: Q4723677 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Probability of the Occurrence of at Least $m$ Events Among $n$ Arbitrary Events
+Normal rank
@@ Property / cites work @@
+An Inequality for Probabilities
@@ Property / cites work: An Inequality for Probabilities / rank @@
+Normal rank
@@ Property / cites work @@
+Laplacian eigenvalues and the maximum cut problem
@@ Property / cites work: Laplacian eigenvalues and the maximum cut problem / rank @@
+Normal rank
@@ Property / cites work @@
+Une propriété extremale des plans projectifs finis dans une classe de codes équidistants
+Normal rank
@@ Property / cites work @@
+L-polytopes and equiangular lines
@@ Property / cites work: L-polytopes and equiangular lines / rank @@
+Normal rank
@@ Property / cites work @@
+HYPERMETRIC GRAPHS
@@ Property / cites work: HYPERMETRIC GRAPHS / rank @@
+Normal rank
@@ Property / cites work @@
+Q3137180
@@ Property / cites work: Q3137180 / rank @@
+Normal rank
@@ Property / cites work @@
+The hypermetric cone is polyhedral
@@ Property / cites work: The hypermetric cone is polyhedral / rank @@
+Normal rank
@@ Property / cites work @@
+Application of cut polyhedra. I
@@ Property / cites work: Application of cut polyhedra. I / rank @@
+Normal rank
@@ Property / cites work @@
+How far apart can the group multiplication tables be?
+Normal rank
@@ Property / cites work @@
+Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
+Normal rank
@@ Property / cites work @@
+A cone of inhomogeneous second-order polynomials
@@ Property / cites work: A cone of inhomogeneous second-order polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+The Empty Sphere
@@ Property / cites work: The Empty Sphere / rank @@
+Normal rank
@@ Property / cites work @@
+Compositions in the bipartite subgraph polytope
@@ Property / cites work: Compositions in the bipartite subgraph polytope / rank @@
+Normal rank
@@ Property / cites work @@
+Q5514188
@@ Property / cites work: Q5514188 / rank @@
+Normal rank
@@ Property / cites work @@
+Bonferroni inequalities
@@ Property / cites work: Bonferroni inequalities / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4208509
@@ Property / cites work: Q4208509 / rank @@
+Normal rank
@@ Property / cites work @@
+Geometric algorithms and combinatorial optimization
+Normal rank
@@ Property / cites work @@
+Weakly bipartite graphs and the max-cut problem
@@ Property / cites work: Weakly bipartite graphs and the max-cut problem / rank @@
+Normal rank
@@ Property / cites work @@
+Finding a Maximum Cut of a Planar Graph in Polynomial Time
+Normal rank
@@ Property / cites work @@
+Bounds for equidistant codes and partial projective planes
+Normal rank
@@ Property / cites work @@
+Q5629416
@@ Property / cites work: Q5629416 / rank @@
+Normal rank
@@ Property / cites work @@
+Hierarchical clustering schemes
@@ Property / cites work: Hierarchical clustering schemes / rank @@
+Normal rank
@@ Property / cites work @@
+Metrics and undirected cuts
@@ Property / cites work: Metrics and undirected cuts / rank @@
+Normal rank
@@ Property / cites work @@
+Half-integral five-terminus flows
@@ Property / cites work: Half-integral five-terminus flows / rank @@
+Normal rank
@@ Property / cites work @@
+Polyhedra related to undirected multicommodity flows
+Normal rank
@@ Property / cites work @@
+Sums of cuts and bipartite metrics
@@ Property / cites work: Sums of cuts and bipartite metrics / rank @@
+Normal rank
@@ Property / cites work @@
+Best Linear Bonferroni Bounds
@@ Property / cites work: Best Linear Bonferroni Bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Q3274182
@@ Property / cites work: Q3274182 / rank @@
+Normal rank
@@ Property / cites work @@
+Equiangular lines
@@ Property / cites work: Equiangular lines / rank @@
+Normal rank
@@ Property / cites work @@
+Q3856789
@@ Property / cites work: Q3856789 / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorial approaches to multiflow problems
@@ Property / cites work: Combinatorial approaches to multiflow problems / rank @@
+Normal rank
@@ Property / cites work @@
+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
+Normal rank
@@ Property / cites work @@
+On a certain distance of sets and the corresponding distance of functions
+Normal rank
@@ Property / cites work @@
+Generalized Radon Transform and Lévy’s Brownian Motion, II
+Normal rank
@@ Property / cites work @@
+Quantum probability - quantum logic
@@ Property / cites work: Quantum probability - quantum logic / rank @@
+Normal rank
@@ Property / cites work @@
+Correlation polytopes: Their geometry and complexity
+Normal rank
@@ Property / cites work @@
+Q3137209
@@ Property / cites work: Q3137209 / rank @@
+Normal rank
@@ Property / cites work @@
+Nonpolyhedral Relaxations of Graph-Bisection Problems
+Normal rank
@@ Property / cites work @@
+Mass transhipment problems and ideal metrics
@@ Property / cites work: Mass transhipment problems and ideal metrics / rank @@
+Normal rank
@@ Property / cites work @@
+Q3851094
@@ Property / cites work: Q3851094 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3818127
@@ Property / cites work: Q3818127 / rank @@
+Normal rank
@@ Property / cites work @@
+A generalized cut-condition for multiflows in matroids
+Normal rank
@@ Property / cites work @@
+Matroids and multicommodity flows
@@ Property / cites work: Matroids and multicommodity flows / rank @@
+Normal rank
@@ Property / cites work @@
+The classification of finite connected hypermetric spaces
+Normal rank
@@ Property / cites work @@
+Q5847989
@@ Property / cites work: Q5847989 / rank @@
+Normal rank