Back to Search
Start Over
An Efficient Framework for Balancing Submodularity and Cost
- Source :
- KDD
- Publication Year :
- 2020
- Publisher :
- arXiv, 2020.
-
Abstract
- In the classical selection problem, the input consists of a collection of elements and the goal is to pick a subset of elements from the collection such that some objective function $f$ is maximized. This problem has been studied extensively in the data-mining community and it has multiple applications including influence maximization in social networks, team formation and recommender systems. A particularly popular formulation that captures the needs of many such applications is one where the objective function $f$ is a monotone and non-negative submodular function. In these cases, the corresponding computational problem can be solved using a simple greedy $(1-\frac{1}{e})$-approximation algorithm. In this paper, we consider a generalization of the above formulation where the goal is to optimize a function that maximizes the submodular function $f$ minus a linear cost function $c$. This formulation appears as a more natural one, particularly when one needs to strike a balance between the value of the objective function and the cost being paid in order to pick the selected elements. We address variants of this problem both in an offline setting, where the collection is known a priori, as well as in online settings, where the elements of the collection arrive in an online fashion. We demonstrate that by using simple variants of the standard greedy algorithm (used for submodular optimization) we can design algorithms that have provable approximation guarantees, are extremely efficient and work very well in practice.<br />Comment: Extended version of KDD 2021 paper
- Subjects :
- FOS: Computer and information sciences
Mathematical optimization
Monotone polygon
Computer science
Generalization
Computer Science - Data Structures and Algorithms
Approximation algorithm
Data Structures and Algorithms (cs.DS)
Function (mathematics)
Maximization
Computational problem
Greedy algorithm
Submodular set function
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- KDD
- Accession number :
- edsair.doi.dedup.....a2905889a5d82aace46a0734b0844ed9
- Full Text :
- https://doi.org/10.48550/arxiv.2002.07782