Submodular optimization problems and greedy strategies: A survey

被引：0
作者：
Yajing Liu
Edwin K. P. Chong
Ali Pezeshki
Zhenliang Zhang
机构：
[1] National Renewable Energy Laboratory (NREL),Department of Electrical and Computer Engineering, and Department of Mathematics
[2] Colorado State University,undefined
[3] Alibaba iDST,undefined
来源：
Discrete Event Dynamic Systems | 2020年 / 30卷
关键词：
Curvature; Greedy strategy; Nash equilibrium; Optimization; Performance; Submodular;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The greedy strategy is an approximation algorithm to solve optimization problems arising in decision making with multiple actions. How good is the greedy strategy compared to the optimal solution? In this survey, we mainly consider two classes of optimization problems where the objective function is submodular. The first is set submodular optimization, which is to choose a set of actions to optimize a set submodular objective function, and the second is string submodular optimization, which is to choose an ordered set of actions to optimize a string submodular function. Our emphasis here is on performance bounds for the greedy strategy in submodular optimization problems. Specifically, we review performance bounds for the greedy strategy, more general and improved bounds in terms of curvature, performance bounds for the batched greedy strategy, and performance bounds for Nash equilibria.
引用
收藏
页码：381 / 412
页数：31
相关论文
共 108 条
  • [1] Ahmed S(2011)Maximizing a class of submodular utility functions Math Program 128 149-169
  • [2] Atamtürk A(2007)Autonomous vehicle-target assignment: A game-theoretical formulation J Dyn Syst Meas Control 129 584-596
  • [3] Arslan G(1957)The simple analytics of welfare maximization Am Econ Rev 47 22-59
  • [4] Marden JR(2003)An inequality for polymatroid functions and its applications Discrete Appl Math 131 255-281
  • [5] Shamma JS(2012)A tight linear time (1/2)-approximation for unconstrained submodular maximization SIAM J Comput 44 255-281
  • [6] Bator FM(2011)Maximizing a submodular set function subject to a matroid constraint SIAM J Comput 40 1740-1766
  • [7] Boros E(1974)The maximal covering location problem Pap Reg Sci 32 101-118
  • [8] Elbassioni K(2006)An efficient approximation for the generalized assignment problem Inf Process Lett 100 162-166
  • [9] Khachiyan L(1984)Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem Discrete Appl Math 7 251-274
  • [10] Buchbinder N(1977)Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms Manag Sci 23 789-810
12345678910