The Worst and the Most Probable Performance of a Class of Set-Covering Algorithms

DOI10.1137/0212021MaRDI QIDQ3668868zbMATH OpenOpenAlexFDO

Authors Vladimir Lifschitz, Boris Pittel

Publication date 1983

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0212021

zbMATH Keywords

analysis of algorithmsrandom treescomplexity boundsasymptotical estimatesworst case behaviorset- coveringprobabilistic behavior

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Cited in

(3)

• Average polynomial time complexity of some NP-complete problems
• To Vladimir Lifschitz on His 65th Birthday
• A note on the complexity of a partition algorithm

This page was built for publication: The Worst and the Most Probable Performance of a Class of Set-Covering Algorithms

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