Optimal approximation for the submodular welfare problem in the value oracle model

By Jan Vondr'ak. Symposium on the Theory of Computing, 2008

613 citations recorded by the source corpus.

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

View Paper: https://www.semanticscholar.org/paper/3a43c0c79f3fdb2490eb87efd299a0c7e8480a91

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

Optimal approximation for submodular and supermodular optimization with bounded curvature (2013, background): “1 Introduction The problem of maximizing a submodular function subject to various constraints is a meta-problem that appears in various settings, from combinatorial auctions [28, 12, 32] and viral marketing in social networks [21] to optimal sensor placement in machine learning”
Submodular maximization by simulated annealing (2010, methodology): “This extension has been used to design an optimal (1 − 1/e)-approximation for the problem of maximizing a monotone submodular function subject to a matroid independence constraint [32, 5], improving the greedy 1/2-approximation of Fisher, Nemhauser and Wolsey [10].”
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (2011, methodology): “The second main technical ingredient of our work (the continuous greedy process) appeared first in [42].”
The Frank-Wolfe Algorithm: A Short Introduction (2023, neutral): “…et al. [49]), image processing (see, e.g., Joulin et al. [50], Tang et al. [75]), quantum physics (see, e.g., Gilbert [41], Designolle et al. [30]), submodular function maximization (see, e.g., Feldman et al. [33], Vondrák [79], Badanidiyuru and Vondrák [5], Mirzasoleiman et al. [60], Hassani…”
Tight approximation algorithms for maximum general assignment problems (2006, neutral): “Recently, Vondrak [29] and Calinescu et al.”
Submodular Function Maximization (2014, background): “However, for the purpose of (constrained) submodular maximization , a diﬀerent extension, pioneered by Vondr´ak (2008) has proven to be very useful: The multilinear extension of f , ˆ f : Thus, ˆ f ( x ) is the expected value of f over sets, where each element i is included independently with…”
Guarantees for Greedy Maximization of Non-submodular Functions with Applications (2017, background): “…S t − 1 F ( S t − 1 ∪ { v } ) − F ( S t − 1 ) ; 4 S t ← S t − 1 ∪ { v ∗ } ; Output: S K decreasing submodular set function 1 , the G REEDY algo-rithm enjoys the multiplicative approximation guarantee of (1 − 1 /e ) (Nemhauser et al., 1978; Sviridenko, 2004; Vondr´ak, 2008; Krause & Golovin, 2012).”
Submodularity and Curvature: The Optimal Algorithm (2010, methodology): “This is a multilinear polynomial with the following properties (see [ 23 ]):”
Non-monotone submodular maximization under matroid and knapsack constraints (2009, methodology): “Furthermore, as shown in Vondr´ak [49], for all i, j ∈ V , ∂ 2 ∂x j ∂x i F ≤ 0 everywhere on [0 , 1] n ; we refer to this condition as continuous submodularity .”
Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract) (2011, methodology): “The continuous greedy algorithm of [16] starts with an empty set, and then only increases the probabilities of elements.”
Generalized Task Markets for Human and Machine Computation (2010, background): “For the superadditive case, an approximation ratio of √ log m m can be achieved (Mirrokni, Schapira, and Vondrak 2008).”
Fast algorithms for maximizing submodular functions (2014, methodology): “The continuous greedy algorithm from [33, 2] runs in continuous time from 0 to 1.”
Online Matching and Ad Allocation (2013, methodology): “An optimal algorithm in the value oracle model was provided by Vondrak in [93] with an approximation factor of 1 − (1)e .”
A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, background): “Most notable is the well studied Submodular Welfare problem (refer to [7], [8], [13]– [15], [17], [18], [30], [38], [44], [47], [48] for previous results on Submodular Welfare and additional closely related variants of the problem).”
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (2012, neutral): “[13] gave non-monotone counterparts of the continuous greedy algorithm of [3], [38].”
Maximizing Non-Monotone Submodular Functions (2011, methodology): “For maximizing monotone submodular functions, optimal approximation algorithms have been developed in the cases of a matroid constraint [49, 6], and multiple knapsack constraints [30].”