| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6876152 | Theoretical Computer Science | 2014 | 8 Pages |
Abstract
In this paper we show a randomized max(2n,Î(1+lnÎ/2))-approximation algorithm using LP rounding, where Î is the maximum degree in the input graph. On the other hand we prove that there exists a constant c such that the minimum rainbow subgraph problem does not have a clnÎ-approximation, unless NPâDTIME(nO(loglogn)).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alexandru Popa,