Probabilistic asymptotic properties of some combinatorial optimization problems

DOI10.1016/0166-218X(85)90037-XzbMath0581.90055MaRDI QIDQ1067976

Ulrich Fincke, Rainer E. Burkard

Publication date: 1985

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

zbMATH Keywords

combinatorial optimizationquadratic assignmentheuristic algorithmsprobabilistic asymptotic behaviourprobabilistic error boundssum- and bottleneck objective function

Mathematics Subject Classification ID

Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

Probabilistic estimates for the generalized maximum satisfiability problem, Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs, The Random QUBO, Asymptotic behavior of the quadratic knapsack problem, Local search with memory: Benchmarking RTS, Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck, A linear ordering problem of sets, Combinational optimization problems for which almost every algorithm is asymptotically optimal, On optimality of a polynomial algorithm for random linear multidimensional assignment problem, Bounds for Random Binary Quadratic Programs, The random quadratic assignment problem, Random assignment problems, Discrete optimization: an Austrian view, Selected topics on assignment problems, A note on the asymptotic behaviour of bottleneck problems, Uncertain programming model for uncertain optimal assignment problem, OR Utopia, An asymptotical study of combinatorial optimization problems by means of statistical mechanics

Uses Software

• LOLIB

Cites Work

• Unnamed Item
• On the Expected Value of a Random Assignment Problem
• Assignment Problems and the Location of Economic Activities
• The asymptotic probabilistic behaviour of quadratic sum assignment problems
• Asymptotic Properties of the Quadratic Assignment Problem
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• On random quadratic bottleneck assignment problems
• P-Complete Approximation Problems
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Optimal control of plotting and drilling machines: A case study