Laitila , J & Moilanen , A 2017 , ' New performance guarantees for the greedy maximization of submodular set functions ' , Optimization Letters , vol. 11 , no. 4 , pp. 655-665 . https://doi.org/10.1007/s11590-016-1039-z
Title: | New performance guarantees for the greedy maximization of submodular set functions |
Author: | Laitila, Jussi; Moilanen, Atte |
Contributor: | University of Helsinki, Department of Mathematics and Statistics University of Helsinki, Biosciences |
Date: | 2017-04 |
Number of pages: | 11 |
Belongs to series: | Optimization Letters |
ISSN: | 1862-4472 |
URI: | http://hdl.handle.net/10138/313036 |
Abstract: | We present new tight performance guarantees for the greedy maximization of monotone submodular set functions. Our main result first provides a performance guarantee in terms of the overlap of the optimal and greedy solutions. As a consequence we improve performance guarantees of Nemhauser et al. (Math Program 14: 265-294, 1978) and Conforti and Cornuejols (Discr Appl Math 7: 251-274, 1984) for maximization over subsets, which are at least half the size of the problem domain. As a further application, we obtain a new tight approximation guarantee in terms of the cardinality of the problem domain. |
Subject: |
Approximation
Cardinality Convex optimization Greedy algorithm Maximization Steepest ascent RESERVE SELECTION FUNCTION SUBJECT ALGORITHM APPROXIMATIONS CONSTRAINT 111 Mathematics |
Rights: |
Total number of downloads: Loading...
Files | Size | Format | View |
---|---|---|---|
1506.00423.pdf | 149.4Kb |
View/ |