Please use this identifier to cite or link to this item:
https://oa.tib.eu/renate/handle/123456789/3459
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.rights.license | 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. | eng |
dc.rights.license | 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. | ger |
dc.contributor.author | Lee, Jon | |
dc.contributor.author | Onn, Shmuel | |
dc.contributor.author | Weismantel, Robert | |
dc.date.available | 2019-06-28T08:25:49Z | |
dc.date.issued | 2008 | |
dc.identifier.uri | https://doi.org/10.34657/2743 | - |
dc.identifier.uri | https://oa.tib.eu/renate/handle/123456789/3459 | |
dc.description.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. | eng |
dc.format | application/pdf | |
dc.language.iso | eng | eng |
dc.publisher | Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach | eng |
dc.relation.ispartofseries | Oberwolfach Preprints (OWP), Volume 2008-10, ISSN 1864-7596 | eng |
dc.subject.ddc | 510 | eng |
dc.title | Nonlinear optimization over a weighted independence system | eng |
dc.type | report | eng |
dc.type | Text | eng |
dc.description.version | publishedVersion | eng |
wgl.contributor | MFO | eng |
wgl.subject | Mathematik | eng |
wgl.type | Report / Forschungsbericht / Arbeitspapier | eng |
dc.relation.doi | https://doi.org/10.14760/OWP-2008-10 | |
dcterms.bibliographicCitation.journalTitle | Oberwolfach Preprints (OWP) | eng |
tib.accessRights | openAccess | eng |
Appears in Collections: | Mathematik |
Files in This Item:
File | Size | Format | |
---|---|---|---|
OWP2008_10.pdf | 238,46 kB | Adobe PDF | View/Open |
Show simple item record
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
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.