From Erdős to algorithms
type: Item
instance of: scholarly article
title: From Erdős to algorithms
zbMATH Open document ID: 0816.90150
DOI: 10.1016/0012-365X(93)E0117-M
published in: Discrete Mathematics
publication date: 1995-02-13T00:00:00Z
review text: The probabilistic method of Paul Erdős proves the existence of an object by showing that an appropriately defined random object has a positive probability of having the desired property. This can lead to a probabilistic algorithm for creating the object. A number of instances are given in this semi-expository paper in which a weight function may be used to derandomize the algorithm, yielding a deterministic efficient algorithm to find the object.
Mathematics Subject Classification ID: 91A99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 91A05
zbMATH DE Number: 722495
zbMATH Keywords: probabilistic algorithm
author: Joel Spencer
MaRDI profile type: Publication
cites work: On 3-chromatic hypergraphs
cites work: Q5724800
cites work: On a combinatorial problem. II
cites work: Q4074927
cites work: On a combinatorial game
cites work: Probabilistic construction of deterministic algorithms: approximating packing integer programs
cites work: Q3481743
cites work: Six Standard Deviations Suffice
cites work: Balancing vectors in the max norm
full work available at URL: 0012-365x(93)e0117-m
OpenAlex ID: W2778477491
description: scientific article; zbMATH DE number 722495