The asymptotic probabilistic behaviour of quadratic sum assignment problems

DOI10.1007/BF01916903zbMath0518.90052MaRDI QIDQ3668301

Rainer E. Burkard, Ulrich Fincke

Publication date: 1983

Published in: Zeitschrift für Operations Research (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmasymptotic probabilistic behaviourquadratic sum assignment problemworst case behavior

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (13)

The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach ⋮ On linear programs with random costs ⋮ A note on asymptotic properties of the quadratic assignment problem ⋮ Quadratic assignment problems ⋮ On optimality of a polynomial algorithm for random linear multidimensional assignment problem ⋮ Random assignment problems ⋮ Selected topics on assignment problems ⋮ Subclasses of solvable problems from classes of combinatorial optimization problems ⋮ A heuristic for quadratic Boolean programs with applications to quadratic assignment problems ⋮ An asymptotical study of combinatorial optimization problems by means of statistical mechanics ⋮ On random quadratic bottleneck assignment problems ⋮ Probabilistic asymptotic properties of some combinatorial optimization problems ⋮ Some recent results in the analysis of greedy algorithms for assignment problems

Cites Work

• Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations
• On the Expected Value of a Random Assignment Problem
• Assignment Problems and the Location of Economic Activities
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem
• On random quadratic bottleneck assignment problems
• P-Complete Approximation Problems
• Numerical investigations on quadratic assignment problems
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: The asymptotic probabilistic behaviour of quadratic sum assignment problems