Robust budget allocation via continuous submodular functions
From MaRDI portal
Abstract: The optimal allocation of resources for maximizing influence, spread of information or coverage, has gained attention in the past years, in particular in machine learning and data mining. But in applications, the parameters of the problem are rarely known exactly, and using wrong parameters can lead to undesirable outcomes. We hence revisit a continuous version of the Budget Allocation or Bipartite Influence Maximization problem introduced by Alon et al. (2012) from a robust optimization perspective, where an adversary may choose the least favorable parameters within a confidence set. The resulting problem is a nonconvex-concave saddle point problem (or game). We show that this nonconvex problem can be solved exactly by leveraging connections to continuous submodular functions, and by solving a constrained submodular minimization problem. Although constrained submodular minimization is hard in general, here, we establish conditions under which such a problem can be solved to arbitrary precision .
Recommendations
Cites work
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 5968956 (Why is no real title available?)
- A tutorial on geometric programming
- Active set algorithms for isotonic regression; a unifying framework
- Adaptive submodularity: theory and applications in active learning and stochastic optimization
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- Approximation algorithms for reliable stochastic combinatorial optimization
- Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
- Conditional gradient algorithms with open loop step size rules
- Constrained maximization of posynomials by geometric programming
- Discrete convex analysis
- Exact bounds for steepest descent algorithms of $L$-convex function minimization
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Finding the nearest point in A polytope
- Geometric Programming for Communication Systems
- Geometric Programming: Methods, Computations and Applications
- Maximizing social influence in nearly optimal time
- Minimizing a Submodular Function on a Lattice
- New algorithms for convex cost tension problem with application to computer vision
- Polymatroids and mean-risk minimization in discrete optimization
- Relative entropy relaxations for signomial optimization
- Rings of sets
- Risk averse submodular utility maximization
- Robust discrete optimization and network flows
- Robust monotone submodular function maximization
- Robust optimization
- Robust solutions of linear programming problems contaminated with uncertain data
- Stochastic Covering and Adaptivity
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- Submodular Function Minimization under Covering Constraints
- Submodular function maximization on the bounded integer lattice
- Submodular functions and optimization.
- Submodular functions: from discrete to continuous domains
- Submodular stochastic probing on matroids
- Subquadratic submodular function minimization
- Supermodular programming on finite lattices
- Templates for convex cone problems with applications to sparse signal recovery
- The limitations of optimization from samples
- Theory and applications of robust optimization
Cited in
(3)
This page was built for publication: Robust budget allocation via continuous submodular functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019911)
