Bicriteria approximation tradeoff for the node-cost budget problem
Abstract
References
Index Terms
- Bicriteria approximation tradeoff for the node-cost budget problem
Recommendations
Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
SWAT '08: Proceedings of the 11th Scandinavian workshop on Algorithm TheoryWe 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 ...
Maximum coverage problem with group budget constraints
We study the maximum coverage problem with group budget constraints (MCG). The input consists of a ground set X, a collection $$\psi $$ź of subsets of X each of which is associated with a combinatorial structure such that for every set $$S_j\in \psi $$...
Randomized Approximation for the Set Multicover Problem in Hypergraphs
Let $$b\in {\mathbb {N}}_{\ge 1}$$b N 1 and let $${\mathcal {H}}=(V,{\mathcal {E}})$$H=(V,E) be a hypergraph with maximum vertex degree $${\varDelta }$$Δ and maximum edge size $$l$$l. A set $$b$$b-multicover in $${\mathcal {H}}$$H is a set of edges $$C \...
Comments
Information & Contributors
Information
Published In
![cover image ACM Transactions on Algorithms](/cms/asset/4a71abb7-f476-4ff4-b8a6-604cc573cbbb/1497290.cover.jpg)
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 325Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in