Facets of the three-index assignment polytope
From MaRDI portal
Publication:2276881
DOI10.1016/0166-218X(89)90014-0zbMath0723.90065OpenAlexW1979743058MaRDI QIDQ2276881
Egon Balas, Matthew J. Saltzman
Publication date: 1989
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(89)90014-0
intersection graphcliquesNP-completelinear programming relaxation3-dimensional matchingfacial structure3-index assignment
Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Discrete location and assignment (90B80)
Related Items
On the orthogonal Latin squares polytope, Approximation algorithms for multi-dimensional assignment problems with decomposable costs, Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem, A survey for the quadratic assignment problem, Using integer programming techniques for the solution of an experimental design problem, Fast separation for the three-index assignment problem, Unnamed Item, Finding the dimension of a non-empty orthogonal array polytope, Improved Computational Approaches and Heuristics for Zero Forcing, Facets of the axial three-index assignment polytope, A survey of dynamic network flows, Combinatorial properties of noninteger vertices of a polytope in a three-index axial assignment problem, On a family of \(0/1\)-polytopes with an NP-complete criterion for vertex nonadjacency relation, Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem, Types of maximum noninteger vertices of the relaxation polyhedron of the four-index axial assignment problem, Integer programming models for the multidimensional assignment problem with star costs, A branch-and-cut procedure for the Udine course timetabling problem, Selected topics on assignment problems, Decomposition and dynamic cut generation in integer linear programming, On multi-index assignment polytopes, Facets of the three-index assignment polytope, Approximation algorithms for three-dimensional assignment problems with triangle inequalities, Linear-time separation algorithms for the three-index assignment polytope, Geometric three-dimensional assignment problems, Randomized parallel algorithms for the multidimensional assignment problem, Clique facets of the axial and planar assignment polytopes, A characterization of odd-hole inequalities related to Latin squares, The multiperiod assignment problem: A multicommodity network flow model and specialized branch and bound algorithm
Cites Work
- Traffic assignment in communication satellites
- Complexity of a 3-dimensional assignment problem
- Facets of the three-index assignment polytope
- Edmonds polytopes and a hierarchy of combinatorial problems
- New Methods in Mathematical Programming—The Solid Transportation Problem
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
- A restricted Lagrangean approach to the traveling salesman problem
- An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice
- Some facets of the simple plant location polytope
- Set Partitioning: A survey
- On the facial structure of set packing polyhedra
- Letter to the Editor—The Multidimensional Assignment Problem
- The Multi-Index Problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
