Distributed strategy selection: A submodular set function maximization approach [PDF]
Automatica, 2023 Constrained submodular set function maximization problems often appear in multi-agent decision-making problems with a discrete feasible set. A prominent example is the problem of multi-agent mobile sensor placement over a discrete domain. Submodular set function optimization problems, however, are known to be NP-hard.
Rezazadeh, Navid, Kia, Solmaz S
openaire +5 more sources
On Equivalence of M$^\natural$-concavity of a Set Function and Submodularity of Its Conjugate [PDF]
, 2017 A fundamental theorem in discrete convex analysis states that a set function is M$^\natural$-concave if and only if its conjugate function is submodular.
Murota, Kazuo, Shioura, Akiyoshi
core +3 more sources
Corrections to “Rigid Network Design Via Submodular Set Function Optimization” [PDF]
IEEE Transactions on Network Science and Engineering, 2020 We provide a correction to our paper "Rigid Network Design Via Submodular Set Function Optimization", which appeared in Volume 2, Issue 3 of the IEEE Transactions on Network Science and Engineering.
Iman Shames, Tyler H. Summers
openaire +2 more sources
Parallelizing greedy for submodular set function maximization in matroids and beyond [PDF]
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019 We consider parallel, or low adaptivity, algorithms for submodular function maximization. This line of work was recently initiated by Balkanski and Singer and has already led to several interesting results on the cardinality constraint and explicit packing constraints.
Chekuri, Chandra, Quanrud, Kent
openaire +4 more sources
Maximizing submodular set function with connectivity constraint: Theory and application to networks [PDF]
2013 Proceedings IEEE INFOCOM, 2013 In this paper, we investigate the wireless network deployment problem, which seeks the best deployment of a given limited number of wireless routers. We found that many goals for network deployment, such as maximizing the number of covered users or areas, or the total throughput of the network, can be modelled with the submodular set function ...
Tung-Wei Kuo +2 more
openaire +3 more sources
An improved approximation algorithm for maximizing a DR-submodular function over a convex set [PDF]
arXiv.org, 2022 Maximizing a DR-submodular function subject to a general convex set is an NP-hard problem arising from many applications in combinatorial optimization and machine learning. While it is highly desirable to design efficient approximation algorithms under this general setting where neither the objective function is monotonic nor the feasible set is down ...
Du, Donglei +4 more
openaire +3 more sources
New Query Lower Bounds for Submodular Function Minimization [PDF]
Information Technology Convergence and Services, 2019 We consider submodular function minimization in the oracle model: given black-box access to a submodular set function $f:2^{[n]}\rightarrow \mathbb{R}$, find an element of $\arg\min_S \{f(S)\}$ using as few queries to $f(\cdot)$ as possible. State-of-the-
Graur, Andrei +3 more
core +3 more sources
Analyzing greedy vaccine allocation algorithms for metapopulation disease models. [PDF]
PLoS Computational BiologyAs observed in the case of COVID-19, effective vaccines for an emerging pandemic tend to be in limited supply initially and must be allocated strategically.
Jeffrey Keithley +3 more
doaj +2 more sources
Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover [PDF]
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013 Stochastic Boolean Function Evaluation is the problem of determining the value of a given Boolean function f on an unknown input x, when each bit of x_i of x can only be determined by paying an associated cost c_i. The assumption is that x is drawn from a given product distribution, and the goal is to minimize the expected cost.
Deshpande, Amol +2 more
openaire +4 more sources
Monotonic Decompositions of Submodular Set Functions
SIAM Journal on Discrete Mathematics26 ...
Bérczi, Kristóf +4 more
openaire +3 more sources