Combinational optimization problems for which almost every algorithm is asymptotically optimal

DOI10.1080/02331939508844086MaRDI QIDQ4836774zbMATH OpenOpenAlexFDO

Authors Wojciech Szpankowski

Publication date 21 June 1995

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331939508844086

zbMATH Keywords

asymptotically optimal solutionlocation problem on graphspattern matchingquadratic assignmentvalue of the optimal solutionvalue of the worst solution

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Applications of mathematical programming (90C90)

Recommendations

• Probabilistic asymptotic properties of some combinatorial optimization problems
• scientific article; zbMATH DE number 3974320
• scientific article; zbMATH DE number 3936510
• An asymptotical study of combinatorial optimization problems by means of statistical mechanics
• Asymptotic Properties of the Quadratic Assignment Problem

Cites work

• A note on asymptotic properties of the quadratic assignment problem
• A probabilistic analysis of a pattern matching problem
• Asymptotic Properties of the Quadratic Assignment Problem
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Maximum Size of a Dynamic Data Structure: Hashing with Lazy Deletion Revisited
• On linear programs with random costs
• Optimization Problems on Graphs with Independent Random Edge Weights
• Probabilistic asymptotic properties of some combinatorial optimization problems
• Random Graphs and Graph Optimization Problems
• The Erdős-Rényi law in distribution, for coin tossing and sequence matching
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem

Cited in

(15)

• Probabilistic asymptotic properties of some combinatorial optimization problems
• A note on probably certifiably correct algorithms
• Posterior agreement for large parameter-rich optimization problems
• Uncertain programming model for uncertain optimal assignment problem
• 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
• Asymptotic behavior of the quadratic knapsack problem
• Cost distributions in large combinatorial optimisation problems
• scientific article; zbMATH DE number 4068626 (Why is no real title available?)
• Bounds for random binary quadratic programs
• Quadratic bottleneck problems
• On optimality of a polynomial algorithm for random linear multidimensional assignment problem
• Selected topics on assignment problems
• Random assignment problems

This page was built for publication: Combinational optimization problems for which almost every algorithm is asymptotically optimal

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