Probabilistic asymptotic properties of some combinatorial optimization problems
A class of combinatorial optimization problems with sum- and bottleneck objective function is described, having the following probabilistic asymptotic behaviour: With probability tending to one the ratio between worst and optimal objective function value approaches one as the size of the problem tends to infinity. Problems belonging to this class are among others quadratic assignment problems, as well as certain combinatorial and graph theoretical optimization problems. The obtained results suggest that even very simple heuristic algorithms incline to yield good solutions for high dimensional problems of this class.
- 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
- A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
- Assignment Problems and the Location of Economic Activities
- Asymptotic Properties of the Quadratic Assignment Problem
- scientific article; zbMATH DE number 3327849 (Why is no real title available?)
- On random quadratic bottleneck assignment problems
- On the Expected Value of a Random Assignment Problem
- Optimal control of plotting and drilling machines: A case study
- P-Complete Approximation Problems
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- The asymptotic probabilistic behaviour of quadratic sum assignment problems
- Probabilistic estimates for the generalized maximum satisfiability problem
- Uncertain programming model for uncertain optimal assignment problem
- OR Utopia
- Local search with memory: Benchmarking RTS
- A linear ordering problem of sets
- A note on the asymptotic behaviour of bottleneck problems
- An asymptotical study of combinatorial optimization problems by means of statistical mechanics
- On a class of optimization problems with no ``efficiently computable solution
- Estimates for the Syracuse problem via a probabilistic model
- On the complexity of nonoverlapping multivariate marginal bounds for probabilistic combinatorial optimization problems
- Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck
- Asymptotic behavior of the quadratic knapsack problem
- Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
- Asymptotics of two integrals from optimization theory and geometric probability
- Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
- Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
- Bounds for random binary quadratic programs
- Probabilistic Combinatorial Optimization: Moments, Semidefinite Programming, and Asymptotic Bounds
- scientific article; zbMATH DE number 1839489 (Why is no real title available?)
- Combinational optimization problems for which almost every algorithm is asymptotically optimal
- The random QUBO
- scientific article; zbMATH DE number 3892936 (Why is no real title available?)
- Discrete optimization: an Austrian view
- Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
- On optimality of a polynomial algorithm for random linear multidimensional assignment problem
- The random quadratic assignment problem
- Efficient estimation of the modified Gromov-Hausdorff distance between unweighted graphs
- Selected topics on assignment problems
- Random assignment problems
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)
