Fetching the paper…
Reading the bibliography…
Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems.
V. Cherenin. Solving some combinatorial problems of optimal planning by the method of successive calculations,
1962
Earlier work this paper cites.
J. Edmonds. Matroids, submodular functions, and certain polyhedra,
1970
Earlier work this paper cites.
G. Cornuéjols, M. Fischer and G. Nemhauser. Location of bank accounts to optimize oat: An analytic study of exact and approximation algorithms,
1977
Earlier work this paper cites.
G. Cornuéjols, M. Fischer and G. Nemhauser. On the uncapacitated location problem,
1977
Earlier work this paper cites.
G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I
1978
Earlier work this paper cites.
G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions II
1978
Earlier work this paper cites.
S. Fujishige. Canonical decompositions of symmetric submodular systems,
1983
Earlier work this paper cites.
V. R. Khachaturov, Mathematical Methods of Regional Programming, Nauka, Moscow (in Russian), 1989
1989
Earlier work this paper cites.
G. P. Cornuéjols, G. L. Nemhauser and L. A. Wolsey. The uncapacitated facility location problem. In
1990
Earlier work this paper cites.
J. G. Oxley, “Matroid theory,” Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992
1992
Earlier work this paper cites.
U. Feige and M. X. Goemans. Approximating the value of two-prover systems, with applications to MAX-2SAT and MAX-DICUT
1995
Earlier work this paper cites.
M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,
1995
Earlier work this paper cites.
C.-W. Ko, J. Lee and M. Queyranne. An exact algorithm for maximum entropy sampling
1995
Earlier work this paper cites.
R. Motwani and P. Raghavan. Randomized Algorithms, Cambridge University Press, 1995
1995
Earlier work this paper cites.
M. Queyranne. A combinatorial algorithm for minimizing symmetric submodular functions, ACM-SIAM
1995
Earlier work this paper cites.
P. Alimonti. Non-oblivious local search for MAX 2-CCSP with application to MAX DICUT, In
1997
Earlier work this paper cites.
A. Frank. Matroids and submodular functions,
1997
Cited alongside, same era.
U. Feige. A threshold of
1998
Cited alongside, same era.
J. Lee. Constrained maximum-entropy sampling
1998
Cited alongside, same era.
A. Ageev and M. Sviridenko. An 0.828 Approximation algorithm for the uncapacitated facility location problem,
1999
Cited alongside, same era.
K. M. Anstreicher, M. Fampa, J. Lee and J. Williams. Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems
1999
Cited alongside, same era.
B. Goldengorin, G. Sierksma, G. Tijsssen and M. Tso. The data correcting algorithm for the minimization of supermodular functions,
1999
Cited alongside, same era.
M. Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint
2004
Later among the works it cites.
E. Hazan, S. Safra and O. Schwartz. On the complexity of approximating
2006
Later among the works it cites.
S. Burer and J. Lee. Solving maximum-entropy sampling problems using factored masks
2007
Later among the works it cites.
G. Calinescu, C. Chekuri, M. Pál and J. Vondrák. Maximizing a monotone submodular function under a matroid constraint,
2007
Later among the works it cites.
U. Feige, V. Mirrokni and J. Vondrák. Maximizing non-monotone submodular functions,
2007
Later among the works it cites.
J. Reichel and M. Skutella, Evolutionary algorithms and matroid optimization problems, in Proceedings of the 9th Genetic and Evolutionary Computation Conference (GECCO’07), 947–954, 2007
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
B. Goldengorin, G. Tijsssen and M. Tso. The maximization of submodular Functions: Old and new proofs for the correctness of the dichotomy algorithm,
1999
Cited alongside, same era.
J. Lee. Semidefinite programming in experimental design. In: H. Wolkowicz, R. Saigal and L. Vandenberghe, editors, ”Handbook of Semidefinite Programming”, International Series in Operations Research and Management Science, Vol. 27, Kluwer, 2000
2000
Cited alongside, same era.
A. Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time,
2000
Cited alongside, same era.
A. Ageev, R. Hassin and M. Sviridenko, An 0.5-approximation algorithm for MAX DICUT with given sizes of parts. SIAM J. Discrete Math. 14 (2001), no. 2, 246–255 (electronic)
2001
Cited alongside, same era.
E. Halperin and U. Zwick. Combinatorial approximation algorithms for the maximum directed cut problem
2001
Cited alongside, same era.
J. Håstad. Some optimal inapproximability results
2001
Cited alongside, same era.
2007
Later among the works it cites.
Encouraging Cooperation in Sharing Supermodular Costs,
A. Schulz, N. Uhan, · 2007
Later among the works it cites.
Optimal marketing strategies over social networks,
J. Hartline, V. Mirrokni and M. Sundararajan · 2008
Later among the works it cites.
A. Krause, A. Singh and C. Guestrin. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies,
2008
Later among the works it cites.
J. Lee, V. Mirrokni, V. Nagarajan and M. Sviridenko. Maximizing Non-Monotone Submodular Functions under Matroid and Knapsack Constraints. IBM Research Report RC24679. 2008
2008
Later among the works it cites.
Z. Svitkina and L. Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. In
2008
Later among the works it cites.
J. Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In
2008
Later among the works it cites.
J. Vondrák, Personal communication, 2008
2008
Later among the works it cites.
M. Goemans, N. Harvey, S. Iwata, V. Mirrokni. Approximating submodular functions everywhere. In
2009
Closest in time.
A. Kulik, H. Shachnai and T. Tamir. Maximizing submodular functions subject to multiple linear constraints
2009
Closest in time.