Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Maximum Weighted Independent Sets with a Budget
verfasst von : Tushar Kalra, Rogers Mathew, Sudebkumar Prasant Pal, Vijay Pandey
Erschienen in: Algorithms and Discrete Applied Mathematics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given a graph G, a non-negative integer k, and a weight function that maps each vertex in G to a positive real number, the Maximum Weighted Budgeted Independent Set (MWBIS) problem is about finding a maximum weighted independent set in G of cardinality at most k. A special case of MWBIS, when the weight assigned to each vertex is equal to its degree in G, is called the Maximum Independent Vertex Coverage (MIVC) problem. In other words, the MIVC problem is about finding an independent set of cardinality at most k with maximum coverage.
Håstad in [Clique is hard to approximate within \(n^{1-\epsilon }\). Foundations of Computer Science, 1996.] showed that there is no \(\frac{1}{n^{1-\epsilon }}\)-factor approximation algorithm for the well-known Maximum Weighted Independent Set (MWIS) problem, where \(\epsilon > 0\), assuming NP-hard problems have no randomized polynomial time algorithms. Being a generalization of the MWIS problem, the above-mentioned inapproximability result applies to MWBIS too. Due to the existence of such inapproximability results for MWBIS in general graphs, in this paper, we restrict our study of MWBIS to the class of bipartite graphs. We show that, unlike MWIS, the MIVC (and thereby the MWBIS) problem in bipartite graphs is NP-hard. Then, we show that the MWBIS problem admits an easy, greedy \(\frac{1}{2}\)-factor approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation. This rules out the possibility of any LP-based algorithm that uses the natural LP relaxation to yield a better factor of approximation.