|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Maximum weighted independent sets with a budget | | Tushar Kalra
; Rogers Mathew
; Sudebkumar Prasant Pal
; Vijay Pandey
; | | Date: |
25 Jun 2015 | | 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 emph{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 emph{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.
Since it is a generalization of the well-known Maximum Weighted Independent
Set (MWIS) problem, MWBIS too does not have any constant factor polynomial time
approximation algorithm assuming $P
eq NP$. In this paper, we study MWBIS in
the context of bipartite graphs. We show that, unlike MWIS, the MIVC (and
thereby the MWBIS) problem in bipartite graphs is NP-hard. We give an $O(nk)$
time $frac{1}{2}$-factor approximation algorithm for MWBIS on bipartite
graphs. We give a natural LP relaxation of MIVC and show that the integrality
gap of this LP is upper bounded by $frac{1}{2} + epsilon$ for bipartite
graphs, where $epsilon$ is any number greater than $0$. For a general graph
$G$, given a $p$-coloring of $G$, we obtain an $O(nk)$ time
$frac{1}{p}$-factor approximation algorithm for MWBIS by extending the
algorithm given for bipartite graphs. | | Source: | arXiv, 1506.7773 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER