Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid |
| |
Institution: | 1. Automatic Control Laboratory, D-ITET, ETH Zürich, ETL K12, Physikstrasse 3, 8092, Zürich, Switzerland;2. Electrical and Computer Engineering Department, University of British Columbia, Vancouver, Canada |
| |
Abstract: | 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. |
| |
Keywords: | Combinatorial optimization Greedy algorithm Matroid theory |
本文献已被 ScienceDirect 等数据库收录! |
|