Average case analysis of greedy algorithms for optimisation problems on set systems

DOI10.1016/0304-3975(95)00242-OMaRDI QIDQ672472zbMATH OpenOpenAlexFDO

Authors Joël Blot, W. Fernandez de la Vega, Rachid Saad, Vangelis Th. Paschos

Publication date 28 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(95)00242-o

zbMATH Keywords

greedy algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• Publication:4866843
• A Tight Analysis of the Greedy Algorithm for Set Cover
• scientific article; zbMATH DE number 3974320
• Analysis of greedy algorithms on graphs with bounded degrees
• scientific article; zbMATH DE number 1323125

Cites work

• scientific article; zbMATH DE number 437559 (Why is no real title available?)
• scientific article; zbMATH DE number 3116771 (Why is no real title available?)
• scientific article; zbMATH DE number 3539474 (Why is no real title available?)
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Induced trees in sparse random graphs
• On the hardness of approximating minimization problems
• Solutions of ordinary differential equations as limits of pure jump markov processes
• Sur la cardinalite maximum des couplages d'hypergraphes aléatoires uniformes

Cited in

(2)

• scientific article; zbMATH DE number 847791 (Why is no real title available?)
• Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis

This page was built for publication: Average case analysis of greedy algorithms for optimisation problems on set systems

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