Randomized algorithms in combinatorial optimization: A survey
type: Item
instance of: scholarly article
title: Randomized algorithms in combinatorial optimization: A survey
zbMATH Open document ID: 0594.90059
DOI: 10.1016/0166-218X(86)90058-2
author: Francesco Maffioli
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: The goal of this survey is to point out possible advantages concerning the use of steps of stochastic nature into heuristics for NP-hard combinatorial optimization problems. The first part of the paper deals with various aspects of randomized local searches, the second one is concerned with random polynomial algorithms and computational complexity aspects.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90-02
zbMATH DE Number: 3956812
zbMATH Keywords: survey
zbMATH Keywords: heuristics
zbMATH Keywords: NP-hard combinatorial optimization
zbMATH Keywords: randomized local searches
zbMATH Keywords: random polynomial algorithms
zbMATH Keywords: computational complexity
reviewed by: Pierre Loridan
MaRDI profile type: Publication
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: A thermodynamically motivated simulation procedure for combinatorial optimization problems
cites work: Unlabelled Partition Systems: Optimization and Complexity
cites work: Some experience in applying a stochastic method to location problems
cites work: Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
cites work: Procedures for Estimating Optimal Solution Values for Large Combinatorial Problems
cites work: Q4145647
cites work: Q4198056
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: A statistical approach to the tsp
cites work: Interval estimation of a global optimum for large combinatorial problems
cites work: On colouring random graphs
cites work: Q4144785
cites work: An Efficient Heuristic Procedure for Partitioning Graphs
cites work: Optimization by Simulated Annealing
cites work: Using branch-and-bound algorithms to obtain suboptimal solutions
cites work: Q4130999
cites work: An Effective Heuristic Algorithm for the Traveling-Salesman Problem
cites work: Matroid matching and some applications
cites work: Q3824109
cites work: A Search Model for Evaluating Combinatorially Explosive Problems
cites work: Q4739657
cites work: Hamiltonian circuits in random graphs
cites work: Probabilistic automata
cites work: Probabilistic algorithm for testing primality
cites work: Computer Solutions to Minimum-Cover Problems
cites work: An Approach to Solving Linear Discrete Optimization Problems
cites work: Probabilistic Turing Machines and Computability
cites work: Q3714899
cites work: Q3851616
full work available at URL: 0166-218x(86)90058-2
OpenAlex ID: W2004272053
description: scientific article; zbMATH DE number 3956812