On the Assignment Polytope

DOI10.1137/1016083zbMath0269.90051OpenAlexW2038964118MaRDI QIDQ3212942

Michel Balinski, Andrew Russakoff

Publication date: 1974

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1016083

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Edge-Connectivity on the Assignment Polytope, Binary choice, subset choice, random utility, and ranking: a unified perspective using the permutahedron, On permutation polytopes, Some relations between neighbourhood graphs for a permutation problem, Partial Permutation and Alternating Sign Matrix Polytopes, Permutation polytopes and indecomposable elements in permutation groups, A proof of the maximal diameter conjecture for the transportation polyhedron, Strong tree-cographs are Birkhoff graphs, Finding the dimension of a non-empty orthogonal array polytope, On the diameter of partition polytopes and vertex-disjoint cycle cover, Hamiltonicity and combinatorial polyhedra, Discrete extremal problems, The hierarchy of circuit diameters and transportation polytopes, Birkhoff--von Neumann Graphs that are PM-Compact, Zu einigen Nachbarschaftsstrukturen fiir Iterationsverfahren zur naherangsweisen Lösung spezieller Reihenfolgeprohleme, The Hirsch conjecture for the fractional stable set polytope, Adjacent Extreme Points Of A Transportation Polytope, Constructing Clustering Transformations, On the Circuit Diameter of Some Combinatorial Polytopes, The monotonic diameter of the perfect matching and shortest path polytopes, Geometry, complexity, and combinatorics of permutation polytopes, The QAP-polytope and the star transformation, On the connectivity of Cayley digraphs, On multi-index assignment polytopes, On the connectivity of Cayley graphs, Convex polyhedra of doubly stochastic matrices. II: Graph of Omega sub(n), Convex polyhedra of doubly stochastic matrices. IV, A note on certain subpolytopes of the assignment polytope associated with circulant graphs, Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function, The diameters of network-flow polytopes satisfy the Hirsch conjecture, On the truncated assignment polytope, A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices, On removing a vertex from the assignment polytope, Good Clusterings Have Large Volume, Linear optimization over permutation groups, Adjacency on the constrained assignment problem, The monotonic diameter of traveling salesman polytopes, Stochastic Load Balancing on Unrelated Machines, Clique facets of the axial and planar assignment polytopes, Adjacency on combinatorial polyhedra, A new linearization method for quadratic assignment problems