New performance guarantees for the greedy maximization of submodular set functions

Näytä kaikki kuvailutiedot



Pysyväisosoite

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

Lähdeviite

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

Julkaisun nimi: New performance guarantees for the greedy maximization of submodular set functions
Tekijä: Laitila, Jussi; Moilanen, Atte
Tekijän organisaatio: Department of Mathematics and Statistics
Biosciences
Päiväys: 2017-04
Kieli: eng
Sivumäärä: 11
Kuuluu julkaisusarjaan: Optimization Letters
ISSN: 1862-4472
DOI-tunniste: https://doi.org/10.1007/s11590-016-1039-z
URI: http://hdl.handle.net/10138/313036
Tiivistelmä: 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.
Avainsanat: Approximation
Cardinality
Convex optimization
Greedy algorithm
Maximization
Steepest ascent
RESERVE SELECTION
FUNCTION SUBJECT
ALGORITHM
APPROXIMATIONS
CONSTRAINT
111 Mathematics
Vertaisarvioitu: Kyllä
Pääsyrajoitteet: openAccess
Rinnakkaistallennettu versio: acceptedVersion


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
1506.00423.pdf 149.4KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot