Bitte benutzen Sie diesen Identifier, um auf die Ressource zu verweisen: https://oa.tib.eu/renate/handle/123456789/3459
Dateien zu dieser Publikation:
Datei GrößeFormat 
OWP2008_10.pdf238,46 kBAdobe PDFAnzeigen/Öffnen
Titel: Nonlinear optimization over a weighted independence system
Autor(en): Lee, JonOnn, ShmuelWeismantel, Robert
Verlagsversion: https://doi.org/10.14760/OWP-2008-10
URI: https://doi.org/10.34657/2743
https://oa.tib.eu/renate/handle/123456789/3459
Erscheinungsjahr: 2008
Publiziert in: Oberwolfach Preprints (OWP), Volume 2008-10, ISSN 1864-7596
Verlag: Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach
Abstract: We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual weights and is independent of the size of the ground set. In contrast, we show that finding an optimal (0-best) solution requires exponential time even in a very special case of the problem.
Publikationstyp: report; Text
Publikationsstatus: publishedVersion
DDC: 510
Lizenz: This document may be downloaded, read, stored and printed for your own use within the limits of § 53 UrhG but it may not be distributed via the internet or passed on to external parties.
Dieses Dokument darf im Rahmen von § 53 UrhG zum eigenen Gebrauch kostenfrei heruntergeladen, gelesen, gespeichert und ausgedruckt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden.
Enthalten in den Sammlungen:Mathematik

Zur Langanzeige
Lee, Jon, Shmuel Onn and Robert Weismantel, 2008. Nonlinear optimization over a weighted independence system. Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach
Lee, J., Onn, S. and Weismantel, R. (2008) Nonlinear optimization over a weighted independence system. Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach. doi: https://doi.org/10.14760/OWP-2008-10.
Lee J, Onn S, Weismantel R. Nonlinear optimization over a weighted independence system. Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach; 2008.
Lee, J., Onn, S., & Weismantel, R. (2008). Nonlinear optimization over a weighted independence system (Version publishedVersion). Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach. https://doi.org/https://doi.org/10.14760/OWP-2008-10
Lee J, Onn S, Weismantel R. Nonlinear optimization over a weighted independence system. Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach; 2008. doi:https://doi.org/10.14760/OWP-2008-10


Alle Publikationen in diesem Repository sind urheberrechtlich geschützt soweit nicht anders angegeben.