Improved Bounds for the Greedy Strategy in Optimization Problems with Curvature

W.T. Tutte, Lecture on matroids, J. Research of the National Bureau of Standards-B. Mathematics and Mathematical Physics 69B (1 and 2) (1965) 1–47

1965

Earlier work this paper cites.

M.L. Fisher, G.L. Nemhauser, L.A. Wolsey, An analysis of approximations for maximizing submodular set functions-II, Math. Programming Study 8 (1978) 73–87

1978

Earlier work this paper cites.

G.L. Nemhauser, L.A. Wolsey, M.L. Fisher, An analysis of approximations for maximizing submodular set functions-I, Math. Programming 14 (1) (1978) 265–294

1978

Earlier work this paper cites.

M. Conforti, G. Cornuéjols, Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem, Discrete Appl. Math. 7 (3) (1984) 251–274

1984

Earlier work this paper cites.

E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan, An inequality for polymatroid functions and its applications, Discrete Appl. Math. 131 (2) (2003) 255–281

2003

Earlier work this paper cites.

J. Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Optimization 2570 (2003) 11–26

2003

Cited alongside, same era.

M. Streeter, D. Golovin, An online algorithm for maximizing submodular functions, in: Proceedings of NIPS: Advances in Neural Information Processing Systems 21, 2008, pp. 67–74

2008

Cited alongside, same era.

J. Vondrák, Submodularity and curvature: The optimal algorithm, RIMS Kokyuroku Bessatsu B23 (2010) 253–266

2010

Cited alongside, same era.

A.P. Singh, A. Guillory, J. Bilmes, On bisubmodular maximization, in: Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, 2012, pp. 1055–1063

2012

Cited alongside, same era.

E. Liu, E.K.P. Chong, and L.L. Scharf, Greedy adaptive linear compression in signal-plus-noise models, IEEE Trans. Inf. Theory 60 (4) (2014), 2269–2280

Original

M. Sviridenko, J. Vondrák, J. Ward, Optimal approximation for submodular and supermodular optimization with bounded curvature, in: Proceedings of the 26th Annual ACM-SIAM Symp. Discrete Algorithms, 2015, pp. 1134–1148

2015

Later among the works it cites.

Y. Liu, E.K.P. Chong, and A. Pezeshki, Bounding the greedy strategy in finite-horizon string optimization, in: Proceedings of the 54th IEEE Conference on Decision and Control, 2015, pp. 3900–3905

2015

Later among the works it cites.

Z. Zhang, E.K.P. Chong, A. Pezeshki, W. Moran, String submodular functions with curvature constraints, IEEE Trans. Autom. Control 61 (3) (2016) 601–616

2016

Later among the works it cites.

Y. Liu, E.K.P. Chong, and A. Pezeshki, Performance bounds for the k k -batch greedy strategy in optimization problems with curvature, in: Proceedings of 2016 American Control Conference, 2016, pp. 7177–7182

2016

Later among the works it cites.