Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

作     者：Karaca, Orcun Tihanyi, Daniel Kamgarpour, Maryam 

作者机构：Swiss Fed Inst Technol Automat Control Lab D ITET ETL K12Phys Str 3 CH-8092 Zurich Switzerland Univ British Columbia Elect & Comp Engn Dept Vancouver BC Canada 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：2021年第49卷第6期

页      面：855-861页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：The authors would like to thank Prof. Victor Il'ev for his helpful feedback on existing bounds for greedy algorithms  Dr. Yatao An Bian for discussions on the literature for properties of set functions 

主　　题：Combinatorial optimization Greedy algorithm Matroid theory 

摘      要：This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and sensor placement problems in control, task allocation problems, video summarization, and many others. We study two greedy heuristics, namely, the forward and reverse greedy. We provide two novel performance guarantees for the approximate solutions obtained by them depending on both submodularity ratio and curvature. (c) 2021 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).