Greed is good

DOI10.1145/195058.195221zbMath1344.68286OpenAlexW2075648490MaRDI QIDQ2817635

Jaikumar Radhakrishnan, Magnús M. Halldórsson

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195221

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items

It is hard to know when greedy is good for finding independent sets, Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP, Improved approximations of independent sets in bounded-degree graphs, On approximation properties of the Independent set problem for degree 3 graphs, Independent sets in graphs with triangles, Optimizing adiabatic quantum program compilation using a graph-theoretic framework, Improved approximations for maximum independent set via approximation chains, The \textsc{max quasi-independent set} problem, Greed is good for deterministic scale-free networks, Minimum Entropy Combinatorial Optimization Problems, Derandomized graph products