New performance guarantees for the greedy maximization of submodular set functions

Show simple item record

dc.contributor.author Laitila, Jussi
dc.contributor.author Moilanen, Atte
dc.date.accessioned 2020-03-05T14:32:01Z
dc.date.available 2020-03-05T14:32:01Z
dc.date.issued 2017-04
dc.identifier.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
dc.identifier.other PURE: 84924686
dc.identifier.other PURE UUID: 46e72389-0c40-4dbe-a69d-253e64533a5c
dc.identifier.other WOS: 000400384200001
dc.identifier.other Scopus: 84966601323
dc.identifier.other ORCID: /0000-0003-3732-8176/work/39022395
dc.identifier.uri http://hdl.handle.net/10138/313036
dc.description.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. en
dc.format.extent 11
dc.language.iso eng
dc.relation.ispartof Optimization Letters
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject Approximation
dc.subject Cardinality
dc.subject Convex optimization
dc.subject Greedy algorithm
dc.subject Maximization
dc.subject Steepest ascent
dc.subject RESERVE SELECTION
dc.subject FUNCTION SUBJECT
dc.subject ALGORITHM
dc.subject APPROXIMATIONS
dc.subject CONSTRAINT
dc.subject 111 Mathematics
dc.title New performance guarantees for the greedy maximization of submodular set functions en
dc.type Article
dc.contributor.organization Department of Mathematics and Statistics
dc.contributor.organization Biosciences
dc.description.reviewstatus Peer reviewed
dc.relation.doi https://doi.org/10.1007/s11590-016-1039-z
dc.relation.issn 1862-4472
dc.rights.accesslevel openAccess
dc.type.version acceptedVersion

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 simple item record