| dc.contributor.author | Lee, Jon | |
| dc.contributor.author | Onn, Shmuel | |
| dc.contributor.author | Weismantel, Robert | |
| dc.date.accessioned | 2008-03-20T12:00:19Z | |
| dc.date.accessioned | 2016-10-05T14:14:08Z | |
| dc.date.available | 2008-03-20T12:00:19Z | |
| dc.date.available | 2016-10-05T14:14:08Z | |
| dc.date.issued | 2008-03-14 | |
| dc.identifier.uri | http://publications.mfo.de/handle/mfo/1131 | |
| dc.description | Research in Pairs 2007 | en_US |
| 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. | en_US |
| dc.language.iso | en | en_US |
| dc.publisher | Mathematisches Forschungsinstitut Oberwolfach | en_US |
| dc.relation.ispartofseries | Oberwolfach Preprints;2008,10 | |
| dc.title | Nonlinear optimization over a Weighted Independence System | en_US |
| dc.type | Preprint | en_US |
| 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. | de |
| 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. | en |
| dc.identifier.doi | 10.14760/OWP-2008-10 | |
| local.scientificprogram | Research in Pairs 2007 | |
| local.series.id | OWP-2008-10 | |
| dc.identifier.urn | urn:nbn:de:101:1-20080627301 | |
| dc.identifier.ppn | 1647467721 | |
