Selected topics on assignment problems
From MaRDI portal
Publication:697571
DOI10.1016/S0166-218X(01)00343-2zbMath1036.90056MaRDI QIDQ697571
Publication date: 17 September 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items
A new mixed integer programming model for curriculum balancing: application to a Turkish university, A survey for the quadratic assignment problem, Tabu search and iterated local search for the cyclic bottleneck assignment problem, Incremental assignment problem, Asymptotic behavior of the expected optimal value of the multidimensional assignment problem, Computational Studies of Randomized Multidimensional Assignment Problems, On the Hamming distance in combinatorial optimization problems on hypergraph matchings, New variable-length data compression scheme for solution representation of meta-heuristics, A distributed simplex algorithm for degenerate linear programs and multi-agent assignments, On optimality of a polynomial algorithm for random linear multidimensional assignment problem, Perfect matchings and extended polymatroid, On the job rotation problem, Random assignment problems, Integer programming models for the multidimensional assignment problem with star costs, Discrete and geometric branch and bound algorithms for~medical image registration, A note on the parity assignment problem, A novel convex dual approach to three-dimensional assignment problem: theoretical analysis, Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique, Test problem generator for the multidimensional assignment problem, A performance guarantee heuristic for electronic components placement problems including thermal effects, A Fast ℒp Spike Alignment Metric, An assignment problem and its application in education domain: a review and potential path, Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search, On a pair of job-machine assignment problems with two stages, Uncertain random assignment problem, Random multi-index matching problems, A dual approach to multi-dimensional assignment problems, Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program, On uniform \(k\)-partition problems, Application of optimal transportation theory to the reconstruction of the early Universe, A MIP model for scheduling India's general elections and police movement
Uses Software
Cites Work
- Average Case Analysis of a Heuristic for the Assignment Problem
- On Representatives of Subsets
- Combinational optimization problems for which almost every algorithm is asymptotically optimal
- Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
- Letter to the Editor—The Multidimensional Assignment Problem
- Algorithm and Average-value Bounds for Assignment Problems
- Bottleneck extrema
- Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- The random linear bottleneck assignment problem
- A Note on Assignment Problems
- The Factorization of Linear Graphs
- The QAP-polytope and the star transformation
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization by Simulated Annealing
- Traffic assignment in communication satellites
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- An improved annealing scheme for the QAP
- Balanced optimization problems
- Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
- A thermodynamically motivated simulation procedure for combinatorial optimization problems
- Alternate strategies for solving bottleneck assignment problems - analysis and computational results
- Matrix multiplication via arithmetic progressions
- On the complexity of decomposing matrices arising in satellite communication
- Probabilistic asymptotic properties of some combinatorial optimization problems
- On lower bounds for a class of quadratic 0,1 programs
- Balancing hydraulic turbine runners - A discrete combinatorial optimization problem
- Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
- Matching is as easy as matrix inversion
- Monge sequences and a simple assignment algorithm
- The complexity of facets resolved
- Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
- Matchings in random regular bipartite digraphs
- Algorithm for the solution of the bottleneck assignment problem
- On the quadratic assignment problem
- Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
- Symmetrization of nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality
- Generating quadratic assignment test problems with known optimal permutations
- The number of 9x9 Latin squares
- An augmenting path method for solving linear bottleneck assignment problems
- An algorithm for the quadratic assignment problem using Benders' decomposition
- A solvable case of the quadratic assignment problem
- The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
- Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
- Certain expected values in the random assignment problem
- An algorithm for the planar three-index assignment problem
- Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
- Location, scheduling, design and integer programming
- QAPLIB - a quadratic assignment problem library
- A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems
- Solution methods and computational investigations for the linear bottleneck assignment problem
- The quadratic assignment problem. Theory and algorithms
- On the applicability of lower bounds for solving rectilinear quadratic assignment problems in parallel
- Semidefinite programming relaxations for the quadratic assignment problem
- Heuristics for biquadratic assignment problems and their computational comparison
- A minimax assignment problem in treelike communication networks
- A greedy genetic algorithm for the quadratic assignment problem
- A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
- Linear-time separation algorithms for the three-index assignment polytope
- On Latin squares and the facial structure of related polytopes
- Complexity of a 3-dimensional assignment problem
- Three-dimensional axial assignment problems with decomposable cost coefficients
- Time-tables, polyhedra and the greedy algorithm
- Perspectives of Monge properties in optimization
- Tabu search for the planar three-index assignment problem
- A dual framework for lower bounds of the quadratic assignment problem based on linearization
- Time-slot assignment for TDMA-systems
- Facets of the three-index assignment polytope
- Massively parallel tabu search for the quadratic assignment problem
- On the SQAP-Polytope
- Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation
- The Quadratic Assignment Problem
- On the Expected Value of a Random Assignment Problem
- Maximal Flow Through a Network
- The Backboard Wiring Problem: A Placement Algorithm
- Assignment Problems and the Location of Economic Activities
- Stochastic Analysis of the Quadratic Assignment Problem
- The asymptotic probabilistic behaviour of quadratic sum assignment problems
- Asymptotic Properties of the Quadratic Assignment Problem
- On linear programs with random costs
- A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
- Algorithms for two bottleneck optimization problems
- Weakly admissible transformations for solving algebraic assignment and transportation problems
- An algorithm to solve them ×n assignment problem in expected timeO(mn logn)
- A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice
- On random quadratic bottleneck assignment problems
- An Algorithm for the Three-Index Assignment Problem
- Tabu Search Applied to the Quadratic Assignment Problem
- A New Lower Bound Via Projection for the Quadratic Assignment Problem
- Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/LP Approach
- P-Complete Approximation Problems
- Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme
- An algebraic approach to assignment problems
- The Reactive Tabu Search