Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

By Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondr'ak. SIAM journal on computing (Print), 2011

919 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

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

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

In Computer Networks and Communications

Citations in the corpus

Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization (2018, methodology): “Impor-tantly, well-known rounding algorithms (Calinescu et al. 2011) can convert a fractional point x to a set S satisfying E [ f ( S )] ≥ F ( x ) ; i.e., the rounding is lossless.”
Submodular Maximization with Cardinality Constraints (2014, methodology): “In order to obtain results for non-monotone objectives, a sequence of works was needed, starting with the celebrated continuous greedy algorithm of [9] which extended [45]’s result to a general matroid constraint by using continuous techniques.”
FLASH: Fast Bayesian Optimization for Data Analytic Pipelines (2016, background): “(3) appears in other fields such as optimal facility location and sensor planning where greedy algorithm is known to have a 1− 1 e approximation guarantee [8, 40].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “an be seen to be the opposite of the convex closure of −F. Note that it cannot be computed in general as this would mean that there are polynomial-time algorithms for submodular function maximization [34]. However, following Prop. 2.6 and its discussion in §2.3, one can always ﬁnd “constant plus mod”
( Please , provide the manuscript number ! ) Capacity Constrained Assortment Optimization under the Markov Chain based Choice Model (2015, positive): “…the revenue function is monotone and submodular, we can exploit the existing machinery for approximately maximizing submodular monotone functions subject to a wide range of constraints (see, for instance, Lee et al. (2010), Buchbinder et al. (2014), Kulik et al. (2013), Calinescu et al. (2011)).”
Submodular Function Maximization (2014, background): “In fact, this results holds even more generally whenever ( V, I ) is a p -extensible system , a combinatorial notion which generalizes the intersections of p matroids (Calinescu et al., 2011).”
Multiwinner Voting with Fairness Constraints (2017, methodology): “Then using the greedy algorithm in [11], we obtain a committee S 2 of size at most”
Online Submodular Maximization with Preemption (2015, background): “[9] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák.”
Submodular function maximization via the multilinear relaxation and contention resolution schemes (2011, methodology): “As we already mentioned , due to [49, 7], there is a (1 − 1/e)-approximation for the problemmax{F (x) : x ∈ P} wheneverF is the multilinear extension of a monotone submodular funct io and P is any solvable polytope.”
Fast algorithms for maximizing submodular functions (2014, methodology): “The proof of this claim is essentially the analysis of the greedy algorithm for a p-system, as in [2].”
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly (2017, methodology): “, 1978], and a more involved algorithm obtains this ratio also for general matroid constraints [Călinescu et al., 2011].”