Randomized algorithms in combinatorial optimization: A survey

DOI10.1016/0166-218X(86)90058-2zbMath0594.90059OpenAlexW2004272053MaRDI QIDQ1077329

Francesco Maffioli

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90058-2

zbMATH Keywords

surveycomputational complexityheuristicsNP-hard combinatorial optimizationrandom polynomial algorithmsrandomized local searches

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (2)

Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms ⋮ Random pseudo-polynomial algorithms for some combinatorial programming problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• A thermodynamically motivated simulation procedure for combinatorial optimization problems
• Probabilistic algorithm for testing primality
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Matroid matching and some applications
• Hamiltonian circuits in random graphs
• Using branch-and-bound algorithms to obtain suboptimal solutions
• Unlabelled Partition Systems: Optimization and Complexity
• Some experience in applying a stochastic method to location problems
• On colouring random graphs
• An Efficient Heuristic Procedure for Partitioning Graphs
• Computational Complexity of Probabilistic Turing Machines
• Procedures for Estimating Optimal Solution Values for Large Combinatorial Problems
• Interval estimation of a global optimum for large combinatorial problems
• A statistical approach to the tsp
• Computer Solutions to Minimum-Cover Problems
• Probabilistic automata
• Probabilistic Turing Machines and Computability
• An Approach to Solving Linear Discrete Optimization Problems
• A Search Model for Evaluating Combinatorially Explosive Problems
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: Randomized algorithms in combinatorial optimization: A survey