Independent Sets in Bounded-Degree Hypergraphs

Autor:	Elena Losievskaja, Magnús M. Halldórsson
Rok vydání:	2007
Předmět:	Greedy coloring Combinatorics Discrete mathematics Degree (graph theory) Independent set Bounded function Set cover problem Maximal independent set Greedy algorithm Greedy randomized adaptive search procedure Mathematics
Zdroj:	Lecture Notes in Computer Science ISBN: 9783540739487 WADS
DOI:	10.1007/978-3-540-73951-7_24
Popis:	In this paper we analyze several approaches to the Maximum Independent Set problem in hypergraphs with degree bounded by Δ. We propose a general technique that reduces the worst case analysis of certain algorithms to their performance in the case of ordinary graphs. This technique allows us to show that the greedy algorithm that corresponds to the classical greedy set cover algorithm has a performance ratio of (Δ + 1)/2. It also allows us to apply results on local search algorithms of graphs to obtain a (Δ + 1)/2 approximation for a weighted case and (Δ + 3)/5 - e approximation for an unweighted case. We improve the bound in the weighted case to [(Δ + 1)/3] using a simple partitioning algorithm. Finally, we show that another natural greedy algorihthm, that adds vertices of minimum degree, achieves only a ratio of Δ - 1, significantly worse than on ordinary graphs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::3c9c0961dd9a52d4c6b66255051e939e https://doi.org/10.1007/978-3-540-73951-7_24 Zobrazit plný text záznamu