𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improved approximations for maximum independent set via approximation chains

✍ Scribed by M. Demange; V.Th. Paschos

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
446 KB
Volume
10
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximating Coloring and Maximum Indep
Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
✍ Michael Krivelevich; Ram Nathaniel; Benny Sudakov πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 120 KB

We discuss approximation algorithms for the coloring problem and the maximum independent set problem in 3-uniform hypergraphs. An algorithm for coloring ˜1r5 Ε½ . ## 3-uniform 2-colorable hypergraphs in O n colors is presented, improving previously known results. Also, for every fixed β₯ ) 1r2, we

Approximation Algorithms for Independent
Approximation Algorithms for Independent Sets in Map Graphs
✍ Zhi-Zhong Chen πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 172 KB

This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1 + Ξ΄ can be achieved by a quadratic-time algorithm for any given con

Recognizing when greed can approximate m
Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
✍ Edith Hemaspaandra; JΓΆrg Rothe πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 511 KB

investigate the computational complexity of the problem of whether the Minimum Degree Greedy Algorithm can approximate a maximum independent set of a graph within a constant factor of r, for fixed rational r > 1. They denote this problem by S, and prove that for each rational r 2 1, S, is coNP-hard.