From Erdős to algorithms

DOI10.1016/0012-365X(93)E0117-MMaRDI QIDQ1344623zbMATH OpenOpenAlexFDO

Authors Joel Spencer

Publication date 13 February 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)e0117-m

zbMATH Keywords

probabilistic algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Game theory (91A99)

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.

Recommendations

• scientific article; zbMATH DE number 53883
• scientific article; zbMATH DE number 742946
• scientific article; zbMATH DE number 4068261
• scientific article; zbMATH DE number 981678
• Erdős magic

Cites work

• Balancing vectors in the max norm
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3188524 (Why is no real title available?)
• On 3-chromatic hypergraphs
• On a combinatorial game
• On a combinatorial problem. II
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Six Standard Deviations Suffice

Cited in

(4)

• scientific article; zbMATH DE number 4068261 (Why is no real title available?)
• scientific article; zbMATH DE number 742946 (Why is no real title available?)
• Erdős magic
• The complexity of explicit constructions

This page was built for publication: From Erdős to algorithms

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