New performance guarantees for the greedy maximization of submodular set functions

Show full item record



Permalink

http://hdl.handle.net/10138/313036

Citation

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:


Files in this item

Total number of downloads: Loading...

Files Size Format View
1506.00423.pdf 149.4Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record