Selected topics on assignment problems

DOI10.1016/S0166-218X(01)00343-2zbMATH Open1036.90056MaRDI QIDQ697571FDOQ697571

Rainer E. Burkard

Publication date: 17 September 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Recommendations

• Assignment Problems
• scientific article; zbMATH DE number 3989103
• A Probabilistic Approach to Solving Assignment Problems
• scientific article; zbMATH DE number 4001850
• Assignment problems: a golden anniversary survey

zbMATH Keywords

complexity bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Abstract computational complexity for mathematical programming problems (90C60) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Discrete location and assignment (90B80)

Cites Work

• The number of 9x9 Latin squares
• Certain expected values in the random assignment problem
• Location, scheduling, design and integer programming
• Solution methods and computational investigations for the linear bottleneck assignment problem
• On the applicability of lower bounds for solving rectilinear quadratic assignment problems in parallel
• A minimax assignment problem in treelike communication networks
• 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
• Time-tables, polyhedra and the greedy algorithm
• A dual framework for lower bounds of the quadratic assignment problem based on linearization
• Time-slot assignment for TDMA-systems
• Massively parallel tabu search for the quadratic assignment problem
• On the SQAP-polytope
• Weakly admissible transformations for solving algebraic assignment and transportation problems
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Average Case Analysis of a Heuristic for the Assignment Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithm and Average-value Bounds for Assignment Problems
• The random linear bottleneck assignment problem
• A Note on Assignment Problems
• Title not available (Why is that?)
• The QAP-polytope and the star transformation
• Alternate strategies for solving bottleneck assignment problems - analysis and computational results
• QAPLIB - a quadratic assignment problem library
• Optimization by Simulated Annealing
• Maximal Flow Through a Network
• Facets of the three-index assignment polytope
• Title not available (Why is that?)
• An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice
• Title not available (Why is that?)
• Letter to the Editor—The Multidimensional Assignment Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of facets resolved
• The Factorization of Linear Graphs
• Title not available (Why is that?)
• 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
• The quadratic assignment problem. Theory and algorithms
• Three-dimensional axial assignment problems with decomposable cost coefficients
• Assignment Problems and the Location of Economic Activities
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• On Representatives of Subsets
• Bottleneck extrema
• Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem
• P-Complete Approximation Problems
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• Matching is as easy as matrix inversion
• On the quadratic assignment problem
• Semidefinite programming relaxations for the quadratic assignment problem
• Complexity of a 3-dimensional assignment problem
• Perspectives of Monge properties in optimization
• Title not available (Why is that?)
• On linear programs with random costs
• Tabu Search Applied to the Quadratic Assignment Problem
• Probabilistic asymptotic properties of some combinatorial optimization problems
• Lower bounds for the quadratic assignment problem based upon a dual formulation
• The quadratic assignment problem
• Title not available (Why is that?)
• Combinational optimization problems for which almost every algorithm is asymptotically optimal
• On the complexity of decomposing matrices arising in satellite communication
• Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
• The Backboard Wiring Problem: A Placement Algorithm
• Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/LP Approach
• Title not available (Why is that?)
• The Reactive Tabu Search
• Title not available (Why is that?)
• An improved annealing scheme for the QAP
• A thermodynamically motivated simulation procedure for combinatorial optimization problems
• Generating quadratic assignment test problems with known optimal permutations
• Title not available (Why is that?)
• Algorithms for two bottleneck optimization problems
• An algorithm for the quadratic assignment problem using Benders' decomposition
• Balanced optimization problems
• A greedy genetic algorithm for the quadratic assignment problem
• An Algorithm for the Three-Index Assignment Problem
• Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
• On Latin squares and the facial structure of related polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Heuristics for biquadratic assignment problems and their computational comparison
• Title not available (Why is that?)
• Algorithm for the solution of the bottleneck assignment problem
• Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
• An augmenting path method for solving linear bottleneck assignment problems
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• Title not available (Why is that?)
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• An algorithm for the planar three-index assignment problem
• Tabu search for the planar three-index assignment problem
• Title not available (Why is that?)
• Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme
• An algebraic approach to assignment problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The asymptotic probabilistic behaviour of quadratic sum assignment problems
• On random quadratic bottleneck assignment problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Traffic assignment in communication satellites
• On the Expected Value of a Random Assignment Problem
• A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic Analysis of the Quadratic Assignment Problem
• Asymptotic Properties of the Quadratic Assignment Problem
• Balancing hydraulic turbine runners - A discrete combinatorial optimization problem
• Symmetrization of nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality
• Title not available (Why is that?)
• On lower bounds for a class of quadratic 0,1 programs
• Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
• Monge sequences and a simple assignment algorithm
• Matchings in random regular bipartite digraphs

Cited In (46)

• Title not available (Why is that?)
• Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program
• Title not available (Why is that?)
• A MIP model for scheduling India's general elections and police movement
• A performance guarantee heuristic for electronic components placement problems including thermal effects
• Application of optimal transportation theory to the reconstruction of the early Universe
• On optimality of a polynomial algorithm for random linear multidimensional assignment problem
• A novel convex dual approach to three-dimensional assignment problem: theoretical analysis
• On uniform \(k\)-partition problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Incremental assignment problem
• An assignment problem and its application in education domain: a review and potential path
• A new mixed integer programming model for curriculum balancing: application to a Turkish university
• Heuristic and exact algorithms for the simultaneous assignment problem
• A survey for the quadratic assignment problem
• A distributed simplex algorithm for degenerate linear programs and multi-agent assignments
• Title not available (Why is that?)
• On a pair of job-machine assignment problems with two stages
• On the Hamming distance in combinatorial optimization problems on hypergraph matchings
• Test problem generator for the multidimensional assignment problem
• Nonlinear assignment problems. Algorithms and applications
• Discrete and geometric branch and bound algorithms for~medical image registration
• A dual approach to multi-dimensional assignment problems
• Tabu search and iterated local search for the cyclic bottleneck assignment problem
• Random assignment problems
• Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique
• A Relaxed Assignment Algorithm For The Quadratic Assignement Problem
• Assignment Problems
• A Fast ℒ_p Spike Alignment Metric
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
• Perfect matchings and extended polymatroid
• New variable-length data compression scheme for solution representation of meta-heuristics
• Integer programming models for the multidimensional assignment problem with star costs
• On the job rotation problem
• Uncertain random assignment problem
• Un algoritmo misto per il problema dell'assegnazione pluridimensionale
• Title not available (Why is that?)
• Computational Studies of Randomized Multidimensional Assignment Problems
• Title not available (Why is that?)
• Random multi-index matching problems
• Title not available (Why is that?)
• A note on the parity assignment problem
• Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search
• Title not available (Why is that?)
• Title not available (Why is that?)

Uses Software

• QAPLIB

This page was built for publication: Selected topics on assignment problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q697571)