Probabilistic asymptotic properties of some combinatorial optimization problems

DOI10.1016/0166-218X(85)90037-XzbMATH Open0581.90055MaRDI QIDQ1067976FDOQ1067976

Authors: Rainer E. Burkard, Ulrich Fincke

Publication date: 1985

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

Recommendations

Combinational optimization problems for which almost every algorithm is asymptotically optimal
An asymptotical study of combinatorial optimization problems by means of statistical mechanics
Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck
A note on the asymptotic behaviour of bottleneck problems
scientific article; zbMATH DE number 3974320

combinatorial optimization heuristic algorithms quadratic assignment probabilistic asymptotic behaviour probabilistic error bounds sum- and bottleneck objective function

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (29)

Uncertain programming model for uncertain optimal assignment problem
Discrete optimization: an Austrian view
Asymptotics of two integrals from optimization theory and geometric probability
The random QUBO
Selected topics on assignment problems
Probabilistic Combinatorial Optimization: Moments, Semidefinite Programming, and Asymptotic Bounds
On optimality of a polynomial algorithm for random linear multidimensional assignment problem
Local search with memory: Benchmarking RTS
A note on the asymptotic behaviour of bottleneck problems
On a class of optimization problems with no ``efficiently computable solution
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
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
Probabilistic estimates for the generalized maximum satisfiability problem
Title not available (Why is that?)
Random assignment problems
Asymptotic behavior of the quadratic knapsack problem
Efficient estimation of the modified Gromov-Hausdorff distance between unweighted graphs
An asymptotical study of combinatorial optimization problems by means of statistical mechanics
OR Utopia
Title not available (Why is that?)
Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
Bounds for random binary quadratic programs
Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
The random quadratic assignment problem
On the complexity of nonoverlapping multivariate marginal bounds for probabilistic combinatorial optimization problems
Estimates for the Syracuse problem via a probabilistic model

Uses Software

LOLIB

This page was built for publication: Probabilistic asymptotic properties of some combinatorial optimization problems

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