Random assignment problems

DOI10.1016/J.EJOR.2007.11.062zbMath1179.90212OpenAlexW2080178200MaRDI QIDQ953417

Pavlo A. Krokhmal, Panos M. Pardalos

Publication date: 20 November 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.11.062

zbMATH Keywords

probabilistic analysisasymptotic analysisquadratic assignment problemlinear assignment problemfitness landscape analysismultidimensional assignment problembottleneck assignment problemrandom assignment problems

Mathematics Subject Classification ID

Continuous location (90B85)

Related Items (13)

Distributionally robust mixed integer linear programs: persistency models with applications ⋮ In and out forests on combinatorial landscapes ⋮ A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability ⋮ Generating QAP instances with known optimum solution and additively decomposable cost function ⋮ Application of graph-theoretic approaches to the random landscapes of the three-dimensional assignment problem ⋮ A new greedy algorithm for the quadratic assignment problem ⋮ On optimality of a polynomial algorithm for random linear multidimensional assignment problem ⋮ The cost of strategy-proofness in school choice ⋮ The random quadratic assignment problem ⋮ Maxima and near-maxima of a Gaussian random assignment field ⋮ Quick or cheap? Breaking points in dynamic markets ⋮ (Non-)obvious manipulability of rank-minimizing mechanisms ⋮ The minimum perfect matching in pseudo-dimension 0 < q < 1

Uses Software

• Unnamed Item

Cites Work

• Quadratic assignment problems
• Traffic assignment in communication satellites
• Selected topics on assignment problems
• A multi-level bottleneck assignment approach to the bus drivers' rostering problem
• QAPLIB-A quadratic assignment problem library
• Asymptotic results for random multidimensional assignment problems
• Asymptotic properties of random multidimensional assignment problems
• A survey for the quadratic assignment problem
• Assignment problems: a golden anniversary survey
• On the number of local minima for the multidimensional assignment problem
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
• Correlated and uncorrelated fitness landscapes and how to tell the difference
• An analysis of a decomposition heuristic for the assignment problem
• Probabilistic asymptotic properties of some combinatorial optimization problems
• The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach
• Order statistics and the linear assignment problem
• A note on asymptotic properties of the quadratic assignment problem
• Matchings in random regular bipartite digraphs
• The multivariate normal distribution
• Generating quadratic assignment test problems with known optimal permutations
• Asymptotics in the random assignment problem
• On the expected optimal value of random assignment problems: Experimental results and open questions
• Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
• Certain expected values in the random assignment problem
• The quadratic assignment problem. Theory and algorithms
• Landscapes and their correlation functions
• On the quality of local search for the quadratic assignment problem
• Heuristics for biquadratic assignment problems and their computational comparison
• A minimax assignment problem in treelike communication networks
• Recent advances in the solution of quadratic assignment problems
• A proof of Parisi's conjecture on the random assignment problem
• Nonlinear assignment problems. Algorithms and applications
• On patching algorithms for random asymmetric travelling salesman problems
• Tracking elementary particles near their primary vertex: A combinatorial approach
• Solving the multisensor data association problem.
• Concentration of measure and isoperimetric inequalities in product spaces
• Time-slot assignment for TDMA-systems
• A note on the asymptotic behaviour of bottleneck problems
• An asymptotical study of combinatorial optimization problems by means of statistical mechanics
• Introduction to the Replica Theory of Disordered Statistical Systems
• The ?(2) limit in the random assignment problem
• GRASP with Path Relinking for Three-Index Assignment
• On the Expected Value of a Random Assignment Problem
• On the expected value of the minimum assignment
• The Backboard Wiring Problem: A Placement Algorithm
• Assignment Problems and the Location of Economic Activities
• Approximation Theorems of Mathematical Statistics
• 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
• The Probabilistic Analysis of a Heuristic for the Assignment Problem
• Algorithms for two bottleneck optimization problems
• On Approximation Methods for the Assignment Problem
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• An algorithm to solve them ×n assignment problem in expected timeO(mn logn)
• On random quadratic bottleneck assignment problems
• An Algorithm for the Three-Index Assignment Problem
• P-Complete Approximation Problems
• An algebraic approach to assignment problems
• Comparison of iterative searches for the quadratic assignment problem
• Constructive bounds and exact expectations for the random assignment problem
• A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
• Random Assignment with Integer Costs
• Combinational optimization problems for which almost every algorithm is asymptotically optimal
• Random multi-index matching problems
• A Lower Bound on the Expected Cost of an Optimal Assignment
• The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems
• Letter to the Editor—The Multidimensional Assignment Problem
• Algorithm and Average-value Bounds for Assignment Problems
• The random linear bottleneck assignment problem
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• On the landscape ruggedness of the quadratic assignment problem
• 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

This page was built for publication: Random assignment problems