Results 1 to 10 of about 11,364 (178)
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
Shaping Level Sets with Submodular Functions [PDF]
, 2010 We consider a class of sparsity-inducing regularization terms based on submodular functions. While previous work has focused on non-decreasing functions, we explore symmetric submodular functions and their \lova extensions. We show that the Lovasz extension may be seen as the convex envelope of a function that depends on level sets (i.e., the set of ...
Francis Bach
+6 more sources
Distributed strategy selection: A submodular set function maximization approach
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.
Navid Rezazadeh, Solmaz S. Kia
openalex +5 more sources
Maximizing Non-monotone Submodular Set Functions Subject to Different\n Constraints: Combined Algorithms [PDF]
Operations Research Letters, 2011 We study the problem of maximizing constrained non-monotone submodular functions and provide approximation algorithms that improve existing algorithms in terms of either the approximation factor or simplicity. Our algorithms combine existing local search and greedy based algorithms. Different constraints that we study are exact cardinality and multiple
Salman Fadaei +2 more
+7 more sources
Maximizing General Set Functions by Submodular Decomposition [PDF]
, 2009 We present a branch and bound method for maximizing an arbitrary set function h mapping 2^V to R. By decomposing h as f-g, where f is a submodular function and g is the cut function of a (simple, undirected) graph G with vertex set V, our original problem is reduced to a sequence of submodular maximization problems.
Kevin M. Byrnes
openalex +3 more sources
Corrections to “Rigid Network Design Via Submodular Set Function Optimization” [PDF]
IEEE Transactions on Network Science and Engineering, 2019 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 Summers
openalex +2 more sources
Submodularity of a Set Label Disagreement Function [PDF]
, 2013 A set label disagreement function is defined over the number of variables that deviates from the dominant label. The dominant label is the value assumed by the largest number of variables within a set of binary variables. The submodularity of a certain family of set label disagreement function is discussed in this manuscript. Such disagreement function
Toufiq Parag
openalex +3 more sources
Generalized budgeted submodular set function maximization [PDF]
Information and Computation, 2021 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.
Francesco Cellinese +3 more
openalex +11 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.
Chandra Chekuri, Kent Quanrud
openalex +3 more sources
Monotonic Decompositions of Submodular Set Functions [PDF]
26 ...
Kristóf Bérczi +4 more
openalex +3 more sources