On the greedy algorithm with random costs

DOI10.1007/BF02592060MaRDI QIDQ4726053zbMATH OpenOpenAlexFDO

Authors Colin McDiarmid

Publication date 1986

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02592060

zbMATH Keywords

balancedbranchinggreedy algorithmhereditary systemsmatroidsprobabilistic analysis

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial optimization (90C27)

Cites work

• Closure in Independence Systems
• General first-passage percolation
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3945879 (Why is no real title available?)
• On linear programs with random costs
• On the value of a random minimum spanning tree problem
• THRESHOLD FUNCTIONS FOR SOME PROPERTIES OF RANDOM SUBSETS OF PROJECTIVE SPACES

Cited in

(5)

• On the power of random greedy algorithms
• On linear programs with random costs
• On the cost of algorithms for random selection
• On randomizing two derandomized greedy algorithms
• On random minimum length spanning trees

This page was built for publication: On the greedy algorithm with random costs

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