On maximizing welfare when utility functions are subadditive

By Uriel Feige. Symposium on the Theory of Computing, 2006

324 citations recorded by the source corpus.

Subfields: Economics and Econometrics, Management Science and Operations Research, Marketing

View Paper: https://www.semanticscholar.org/paper/79a94936b70dd7fdacb3602298762f14ee219201

How researchers see this paper

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

In Economics and Econometrics

In Management Science and Operations Research

In Marketing

Citations in the corpus

Robust Submodular Observation Selection (2008, background): “While such problems are NP-hard in general (Feige, 1998), Wolsey (1982) shows that the greedy algorithm, that starts with the empty set (A = / 0) and iteratively adds the element s increasing the score the most until F(A) = F(V ), achieves near-optimal performance on this problem.”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “We are by no means exhaustive and other applications may be found in facility location [50, 51, 1], game theory [66], document summarization [132], social networks [118], or clustering [159].”
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract) (2007, methodology): “Extension f+: Our first candidate for f̃ is an extension similar to the objective function of the “Configuration LP” [10,7,8].”
Generalized Task Markets for Human and Machine Computation (2010, background): “The problem has been transformed into linear programming problem (Feige 2006), with the rounding of fractional solutions, achieving an approximation ratio of 1 2 .”
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (2011, methodology): “In this model, the (1−1/e)-approximation has been subsequently generalized to all fractionally subadditive functions [14] and the ratio for submodular functions has been improved to 1− 1/e+ δ for some fixed δ > 0 [16].”
Fast algorithms for maximizing submodular functions (2014, background): “Let us mention welfare maximization in combinatorial auctions, where the objective function captures the notion of utility function with diminishing returns [27, 4, 6, 8, 33].”
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).”