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

DOI10.1016/0304-3975(95)00242-OzbMATH Open0873.68073OpenAlexW2018062626MaRDI QIDQ672472FDOQ672472

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

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

zbMATH Keywords

greedy algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Cites Work

• Title not available (Why is that?)
• Solutions of ordinary differential equations as limits of pure jump markov processes
• Title not available (Why is that?)
• On the hardness of approximating minimization problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Induced trees in sparse random graphs
• Sur la cardinalite maximum des couplages d'hypergraphes aléatoires uniformes
• Title not available (Why is that?)

Cited In (2)

• Title not available (Why is that?)
• 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)