New performance guarantees for the greedy maximization of submodular set functions

Visa fullständig post



Permalänk

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

Titel: New performance guarantees for the greedy maximization of submodular set functions
Författare: Laitila, Jussi; Moilanen, Atte
Upphovmannens organisation: Department of Mathematics and Statistics
Biosciences
Datum: 2017-04
Språk: eng
Sidantal: 11
Tillhör serie: Optimization Letters
ISSN: 1862-4472
DOI: https://doi.org/10.1007/s11590-016-1039-z
Permanenta länken (URI): http://hdl.handle.net/10138/313036
Abstrakt: 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
Referentgranskad: Ja
Användningsbegränsning: openAccess
Parallelpublicerad version: acceptedVersion


Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
1506.00423.pdf 149.4Kb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post