RECORD
Generalized budgeted submodular set function maximization
Data Structures and Algorithms · Submitted 9 Aug 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim If we set $\beta=\frac{1}{\alpha}\ln \left(\frac{1}{2\epsilon}\right)$, the algorithm achieves an approximation factor of $\frac{1}{2}-\epsilon$, for any arbitrarily small $\epsilon>0$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
In this paper we consider a generalization of the well-known budgeted maximum coverage problem. We are given a ground set of elements and a set of bins. The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. Each bin has its own cost and the cost of each element depends on its associated bin. The profit is measured by a monotone submodular function over the elements. We first present an algorithm that guarantees an approximation factor of $\frac{1}{2}\left(1-\frac{1}{e^\alpha}\right)$, where $\alpha \leq 1$ is the approximation factor of an algorithm for a sub-problem. We give two polynomial-time algorithms to solve this sub-problem. The first one gives us $\alpha=1- \epsilon$ if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. The second one guarantees $\alpha=1-\frac{1}{e}-\epsilon$ for the general case. The gap between our approximation guarantees and the known inapproximability bounds is $\frac{1}{2}$. We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor $\beta\geq 1$ to guarantee a $\frac{1}{2}\left(1-\frac{1}{e^{\alpha\beta}}\right)$-approximation. If we set $\beta=\frac{1}{\alpha}\ln \left(\frac{1}{2\epsilon}\right)$, the algorithm achieves an approximation factor of $\frac{1}{2}-\epsilon$, for any arbitrarily small $\epsilon>0$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In this paper we consider a generalization of the well-known budgeted maximum coverage problem. | background 0.75 | 0.57 | 0.04 | asserted 0.93 |
| s1 | We are given a ground set of elements and a set of bins. | background 0.87 | 0.19 | 0.01 | asserted 0.97 |
| s2 | The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. | background 0.75 | 0.29 | 0.06 | asserted 0.99 |
| s3 | Each bin has its own cost and the cost of each element depends on its associated bin. | background 0.95 | 0.22 | 0.02 | asserted 1.00 |
| s4 | The profit is measured by a monotone submodular function over the elements. | background 0.90 | 0.22 | 0.03 | asserted 1.00 |
| s5 | We first present an algorithm that guarantees an approximation factor of $\frac{1}{2}\left(1-\frac{1}{e^\alpha}\right)$, where $\alpha \leq 1$ is the approximation factor of an algorithm for a sub-problem. | result 0.62 | 0.94 | 0.47 | asserted 1.00 |
| s6 | We give two polynomial-time algorithms to solve this sub-problem. | contribution 0.53 | 0.95 | 0.04 | asserted 1.00 |
| s7 | The first one gives us $\alpha=1- \epsilon$ if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. | result 0.80 | 0.89 | 0.07 | asserted 1.00 |
| s8 | The second one guarantees $\alpha=1-\frac{1}{e}-\epsilon$ for the general case. | result 0.79 | 0.96 | 0.10 | asserted 1.00 |
| s9 | The gap between our approximation guarantees and the known inapproximability bounds is $\frac{1}{2}$. | result 0.35 | 0.69 | 0.13 | asserted 1.00 |
| s10 | We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor $\beta\geq 1$ to guarantee a $\frac{1}{2}\left(1-\frac{1}{e^{\alpha\beta}}\right)$-approximation. | contribution 0.91 | 0.95 | 0.13 | asserted 1.00 |
| s11 | If we set $\beta=\frac{1}{\alpha}\ln \left(\frac{1}{2\epsilon}\right)$, the algorithm achieves an approximation factor of $\frac{1}{2}-\epsilon$, for any arbitrarily small $\epsilon>0$. | result 0.95 | 0.93 | 0.25 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
In this paper we consider a generalization of the well-known budgeted maximum coverage problem. We are given a ground set of elements and a set of bins. The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. Each bin has its own cost and the cost of each element depends on its associated bin. The profit is measured by a monotone submodular function over the elements. We first present an algorithm that guarantees an approximation factor of $\frac{1}{2}\left(1-\frac{1}{e^\alpha}\right)$, where $\alpha \leq 1$ is the approximation factor of an algorithm for a sub-problem. We give two polynomial-time algorithms to solve this sub-problem. The first one gives us $\alpha=1- \epsilon$ if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. The second one guarantees $\alpha=1-\frac{1}{e}-\epsilon$ for the general case. The gap between our approximation guarantees and the known inapproximability bounds is $\frac{1}{2}$. We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor $\beta\geq 1$ to guarantee a $\frac{1}{2}\left(1-\frac{1}{e^{\alpha\beta}}\right)$-approximation. If we set $\beta=\frac{1}{\alpha}\ln \left(\frac{1}{2\epsilon}\right)$, the algorithm achieves an approximation factor of $\frac{1}{2}-\epsilon$, for any arbitrarily small $\epsilon>0$.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.