Complexity of a 3-dimensional assignment problem
From MaRDI portal
Publication:1837625
DOI10.1016/0377-2217(83)90078-4zbMath0507.90057OpenAlexW1965178295WikidataQ57401637 ScholiaQ57401637MaRDI QIDQ1837625
Publication date: 1983
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0377-2217(83)90078-4
computational complexityNP-completenessbipartite graphsperfect matchings3-dimensional assignment problem
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Related Items (39)
An algorithm for the planar three-index assignment problem ⋮ Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph ⋮ Index Matrices as a Cost Optimization Tool of Resource Provisioning in Uncertain Cloud Computing Environment ⋮ Complexity of a disjoint matching problem on bipartite graphs ⋮ On linear programs with random costs ⋮ A survey for the quadratic assignment problem ⋮ A preemptive open shop scheduling problem with one resource ⋮ Arrays of distinct representatives --- a very simple NP-complete problem ⋮ Cycle-based reducibility of multi-index transport-type systems of linear inequalities ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Tool switching problems in the context of overlay printing with multiple colours ⋮ A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem ⋮ A new greedy algorithm for the quadratic assignment problem ⋮ Tool switching problems with tool order constraints ⋮ Round robin tournaments and three index assignments ⋮ A survey of dynamic network flows ⋮ Three-index linear programs with nested structure ⋮ Envy-free matchings with lower quotas ⋮ On complexity of special maximum matchings constructing ⋮ The constant objective value property for multidimensional assignment problems ⋮ Decomposition method for solving a three-index planar assignment problem ⋮ Multiple criteria mixed-integer programming for incorporating multiple factors into the development of master operating theatre timetables ⋮ A reduction approach to the repeated assignment problem ⋮ Polyhedral combinatorics of multi-index axial transportation problems ⋮ Selected topics on assignment problems ⋮ Efficient algorithms for three‐dimensional axial and planar random assignment problems ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ Time-slot assignment for TDMA-systems ⋮ A new class of facets for the Latin square polytope ⋮ On multi-index assignment polytopes ⋮ Facets of the three-index assignment polytope ⋮ Linear-time separation algorithms for the three-index assignment polytope ⋮ Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms ⋮ On Latin squares and the facial structure of related polytopes ⋮ Lower bounds for the axial three-index assignment problem ⋮ A variant of time minimizing assignment problem ⋮ On the complexity of decomposing matrices arising in satellite communication ⋮ 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
This page was built for publication: Complexity of a 3-dimensional assignment problem
