Name
Abstract | ||
|---|---|---|
We consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. The goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given budget. The best result known prior to this work guaranteed a (2,O(logn)) bicriteria approximation, i.e. the solution's profit is at least a fraction of $\frac{1}{O(\log n)}$ of an optimum solution respecting the budget, while its cost is at most twice the given budget. We improve these results and present a bicriteria tradeoff that, given any 茂戮驴茂戮驴 (0,1], guarantees a $(1+\varepsilon,O(\frac{1}{\varepsilon}\log n))$-approximation. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1497290.1497295 | ACM Transactions on Algorithms (TALG) |
Keywords | DocType | Volume |
bicriteria tradeoff,maximum total profit,total cost,best result,optimum solution,profit function,node-cost budget problem,log n,bicriteria approximation tradeoff,bicriteria approximation,connected subset,optimization problem,approximation algorithms,profitability | Conference | 5 |
Issue | ISSN | Citations |
2 | 1549-6325 | 1 |
PageRank | References | Authors |
0.39 | 12 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuval Rabani | 1 | 2265 | 274.98 |
| Gabriel Scalosub | 2 | 103 | 10.41 |