Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

By Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondr'ak. Conference on Integer Programming and Combinatorial Optimization, 2007

478 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/fac823b4e68c4a177853d4ff6fe7579ec5c3bdf0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, methodology): “The continuous greedy algorithm of [7] starts with an empty solution and at each step moves by a small δ in the direction of a feasible point x ∈ P .”
Maximizing Non-Monotone Submodular Functions (2011, methodology): “A (1 − 1/e)-approximation has been also obtained for a knapsack constraint [36], and for a special class of submodular functions under a matroid constraint [3].”
FemtoCaching: Wireless video content delivery through distributed caching helpers (2011, methodology): “In the second part, the fractional solution of the continuous problem is rounded using a technique called Pipage rounding [14].”
Optimal approximation for submodular and supermodular optimization with bounded curvature (2013, methodology): “Such a vector exists because 1O is one possible candidate (as in the analysis of [5]).”
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (2011, methodology): “Instead of checking which direction is more profitable (as in [3]), we make the choice random.”
Learning Mixtures of Submodular Shells with Application to Document Summarization (2012, background): “arbitrary score function. The reason is that the submodular maximization problem, even under many constrained settings, can be solved eciently and near-optimally with rigorous performance guarantees [36, 13, 25, 2, 11]. The hypothesis function we consider takes the following linear discriminant form”
Submodular maximization by simulated annealing (2010, methodology): “It is known due to [4, 5, 33] that any fractional solution x ∈ P (F) where F are either all subsets, or independent sets in a matroid, or matroid bases, can be rounded to an integral solution S ∈ F such that f(S) ≥ F (x).”
Tight approximation algorithms for maximum general assignment problems (2006, methodology): “Finally, we note that a modified variant of the reduction given from GAP to SFMM in Section 3 also gives an alternative 1 2 − -approximation algorithm for KMed [4].”
Efficient Informative Sensing using Multiple Robots (2014, background): “, 2007b), we realized that our sequential-allocation procedure is an instance of maximizing a submodular function subject to a matroid constraint (Calinescu et al., 2007).”
Submodular Function Maximization (2014, background): “…traces the continuous particle, parameterized as a function x : [0 , 1] → F , originating at x (0) = 0 , and following the diﬀerential equation Calinescu et al. (2011) prove that for matroid polytopes F , it holds that thus at time 1, the particle has reached a point which provides a (1 −…”