Fetching the paper…
Reading the bibliography…
We consider the problem of maximizing a non-negative submodular set function $f:2^N \rightarrow \mathbb{R}_+$ over a ground set $N$ subject to a variety of packing type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections.
Approximate algorithms for some generalized knapsack problems
A. K. Chandra, D. S. Hirschberg, and C. K. Wong · 1976
Earlier work this paper cites.
Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms
G. Cornuejols, M. L. Fisher and G. Nemhauser · 1977
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions - II
M. L. Fisher, G. L. Nemhauser and L. A. Wolsey · 1978
Earlier work this paper cites.
Best algorithms for approximating the maximum of a submodular set function
G. L. Nemhauser and L. A. Wolsey · 1978
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions - I
G. L. Nemhauser, L. A. Wolsey and M. L. Fisher · 1978
Earlier work this paper cites.
The complexity of enumeration and reliability problems
L.G. Valiant · 1979
Earlier work this paper cites.
Submodular functions and convexity
L. Lovász · 1983
Earlier work this paper cites.
Approximation algorithms for the m m -dimensional 0 0 - 1 1 knapsack problem: worst-case and probabilistic analyses
A. M. Frieze and M. R. B. Clarke · 1984
Earlier work this paper cites.
Primal-dual approximation algorithms for integral flow and multicut in trees
N. Garg. V. V. Vazirani, M. Yannakakis · 1993
Earlier work this paper cites.
A threshold of ln n \ln n for approximating set cover
U. Feige · 1998
Earlier work this paper cites.
Approximating disjoint-path problems using greedy algorithms and Packing Integer Programs
S. G. Kolliopoulos and C. Stein · 1998
Earlier work this paper cites.
Clique is hard to approximate within n 1 − ε n^{1-\varepsilon}
J. Håstad · 1999
Earlier work this paper cites.
Improved approximation algorithms for resource allocation
G. Calinescu, A. Chakrabarti, H. Karloff and Y. Rabani · 2001
Earlier work this paper cites.
New approaches to covering and packing problems
A. Srinivasan · 2001
Earlier work this paper cites.
Multicommodity demand flow in a tree and packing integer programs
C. Chekuri, M. Mydlarz and F. B. Shepherd · 2003
Earlier work this paper cites.
Combinatorial Optimization - Polyhedra and Efficiency
A. Schrijver · 2003
Earlier work this paper cites.
Pipage rounding: a new method of constructing algorithms with proven performance guarantee
A. Ageev and M. Sviridenko · 2004
Earlier work this paper cites.
A note on maximizing a submodular set function subject to knapsack constraint
M. Sviridenko · 2004
Earlier work this paper cites.
Approximation algorithms for allocation problems: Improving the factor of 1 − 1 / e 1-1/e
U. Feige and J. Vondrák · 2006
Cited alongside, same era.
Maximizing a submodular set function subject to a matroid constraint
G. Calinescu, C. Chekuri, M. Pál and J. Vondrák · 2007
Cited alongside, same era.
Approximation algorithms for the unsplittable flow problem
A. Chakrabarti, C. Chekuri, A. Gupta and A. Kumar · 2007
Cited alongside, same era.
Maximizing non-monotone submodular functions
U. Feige, V. Mirrokni and J. Vondrák · 2007
Cited alongside, same era.
Submodularity in combinatorial optimization
J. Vondrák · 2007
Cited alongside, same era.
The Probabilistic Method
N. Alon and J. Spencer · 2008
Cited alongside, same era.
Dependent randomized rounding via exchange properties of combinatorial structures
C. Chekuri, J. Vondrák and R. Zenklusen · 2010
Later among the works it cites.
The submodular welfare problem with demand queries
U. Feige and J. Vondrák · 2010
Later among the works it cites.
Robust and MaxMin optimization under matroid and knapsack uncertainty sets
A. Gupta, V. Nagarajan and R. Ravi · 2010
Later among the works it cites.
Constrained non-monotone submodular maximization: Offline and secretary algorithms
A. Gupta, A. Roth, G. Schoenebeck and K. Talwar · 2010
Later among the works it cites.
Approximations for monotone and non-monotone submodular maximization with knapsack constraints
A. Kulik, H. Shachnai and T. Tamir · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions
V. Mirrokni, M. Schapira and J. Vondrák · 2008
Cited alongside, same era.
Optimal approximation for the submodular welfare problem in the value oracle model
J. Vondrák · 2008
Cited alongside, same era.
Approximation algorithms for maximum independent set of pseudo-disks
T. Chan and S. Har-Peled · 2009
Cited alongside, same era.
Sequential posted pricing and multi-parameter mechanism design
S. Chawla, J. Hartline, D. Malec and B. Sivan · 2009
Cited alongside, same era.
UFP in paths and trees and column-restricted packing integer programs
C. Chekuri, A. Ene and N. Korula · 2009
Cited alongside, same era.
Maximizing submodular set functions subject to multiple linear constraints
A. Kulik, H. Shachnai and T. Tamir · 2009
Cited alongside, same era.
Matroid matching: the power of local search
J. Lee, M. Sviridenko and J. Vondrák · 2010
Later among the works it cites.
A note on concentration of submodular functions
J. Vondrák · 2010
Later among the works it cites.
Maximizing a monotone submodular set function subject to a matroid constraint
G. Calinescu, C. Chekuri, M. Pál and J. Vondrák · 2011
Closest in time.
Submodular function maximization via the multilinear relaxation and contention resolution schemes
C. Chekuri, J. Vondrák and R. Zenklusen · 2011
Closest in time.
Submodular function maximization via the multilinear relaxation and contention resolution schemes
C. Chekuri, J. Vondrák and R. Zenklusen · 2011
Closest in time.
A unified continuous greedy algorithm for submodular maximization
M. Feldman, J. Naor, R. Schwartz · 2011
Closest in time.
Submodular maximization by simulated annealing
S. Oveis Gharan and J. Vondrák · 2011
Closest in time.
Mechanism design via correlation gap
Q. Yan · 2011
Closest in time.
Geometric packing under non-uniform constraints
A. Ene, S. Har-Peled and B. Raichel · 2012
Closest in time.
Combinatorial Optimization: Theory and Algorithms
B. Korte and J. Vygen · 2012
Closest in time.
Approximations for monotone and nonmonotone submodular maximization with knapsack constraints
A. Kulik, H. Shachnai and T. Tamir · 2013
Closest in time.
Symmetry and approximability of submodular maximization problems
J. Vondrák · 2013
Closest in time.