scientific article; zbMATH DE number 3989103
Approximate algorithmsaverage performancecomputational complexityexact algorithmslinear assignment problemsNP-hard casesrandomly generated test problemssurvey
Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27)
[For the entire collection see Zbl 0599.00013.] The paper presents a survey on linear assignment problems. Both polynomially solvable cases (min-sum assignment problem, min-max assignment problem, balanced assignment problem) and NP-hard cases (generalized assignment problem) are considered. The most efficient exact algorithms from the literature are described and compared both through their computational complexity and their average performance on randomly generated test problems. Approximate algorithms for the generalized assignment problem are also discussed.
- Statistical applications of linear assignment
- Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem
- A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems
- A survey of algorithms for the generalized assignment problem
- Heuristic sensitivity analysis in a combinatoric environment: An exposition and case study
- Constrained weighted matchings and edge coverings in graphs
- Computing improved optimal solutions to max-min flexible constraint satisfaction problems
- Some recent results in the analysis of greedy algorithms for assignment problems
- A robust heuristic for the generalized assignment problem
- A genetic algorithm for the generalised assignment problem
- The \(k\)-cardinality assignment problem
- A note on the complexity of the asymmetric traveling salesman problem
- Effective algorithm and heuristic for the generalized assignment problem.
- Heuristic and exact algorithms for the simultaneous assignment problem
- Linear assignment procedures
- Nonlinear assignment problems. Algorithms and applications
- An exact algorithm for the minimum squared load assignment problem
- Critical objective function values in linear sum assignment problems
- Single-machine scheduling with supporting tasks
- Linear assignment problems in combinatorial optimization
- A labeling algorithm to solve the assignment problem
- Algorithms and codes for dense assignment problems: The state of the art
- A distributed exact algorithm for the multiple resource constrained sequencing problem
- Solving the rectangular assignment problem and applications
- Cut-and-solve: An iterative search strategy for combinatorial optimization problems
- A new model and hybrid approach for large scale inventory routing problems
- An algorithm for ranking assignments using reoptimization
- On multi-index assignment polytopes
- Linear and semi-assignment problems: A core oriented approach
- Exact algorithms for the imbalanced time minimizing assignment problem
- Prioritizing replenishments of the piece picking area
- Two kinds of constrained assignment problems
- scientific article; zbMATH DE number 3883952 (Why is no real title available?)
- Technical Note—A Note on Parametric Analysis in Linear Assignment
- Assignment Problems
- scientific article; zbMATH DE number 3900504 (Why is no real title available?)
- scientific article; zbMATH DE number 4001850 (Why is no real title available?)
- Ein Simplex-Algorithmus für das partitionsbeschränkte Zuordnungsproblem. (A simplex algorithm for the partition-restricted assignment problem)
- The linear assignment problem
- scientific article; zbMATH DE number 4127004 (Why is no real title available?)
- A Minimum-Cost Analysts Assignment Model for Asset Evaluation of Insolvent Saving and Loan Institutions
- scientific article; zbMATH DE number 1134606 (Why is no real title available?)
- Vector assignment problems: A general framework
- The constrained minimax linear assignment problem
- On the linear assignment problem for special matrices
- A heuristic for the time constrained asymmetric linear sum assignment problem
- New assignment problem for decision making
- A note on the parity assignment problem
- scientific article; zbMATH DE number 2239572 (Why is no real title available?)
- Iterative state-space reduction for flexible computation
- A note on the exact solution of the minimum squared load assignment problem
- Computing fair and bottleneck matchings in geometric graphs
- LoCoMotif: discovering time-warped motifs in time series
- Hardness and algorithms for several new optimization problems on the weighted massively parallel computation model
- Logic-based benders decomposition methods for the distributed permutation flow shop scheduling problem with production and transportation cost
- Selected topics on assignment problems
- On dual solutions of the linear assignment problem
- Minimum deviation and balanced optimization: A unified approach
- Generalized pole placement via static output feedback: a methodology based on projections
- Spatio-temporal multi-robot routing
- Worst case examples of an exterior point algorithm for the assignment problem
- Repulsive assignment problem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3751373)