Zur Kurzanzeige

dc.contributor.authorLee, Jon
dc.contributor.authorOnn, Shmuel
dc.contributor.authorWeismantel, Robert
dc.date.accessioned2008-03-20T12:00:19Z
dc.date.accessioned2016-10-05T14:14:08Z
dc.date.available2008-03-20T12:00:19Z
dc.date.available2016-10-05T14:14:08Z
dc.date.issued2008-03-14
dc.identifier.urihttp://publications.mfo.de/handle/mfo/1131
dc.descriptionResearch in Pairs 2007en_US
dc.description.abstractWe 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.isoenen_US
dc.publisherMathematisches Forschungsinstitut Oberwolfachen_US
dc.relation.ispartofseriesOberwolfach Preprints;2008,10
dc.titleNonlinear optimization over a Weighted Independence Systemen_US
dc.typePreprinten_US
dc.rights.licenseDieses 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.licenseThis 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.doi10.14760/OWP-2008-10
local.scientificprogramResearch in Pairs 2007
local.series.idOWP-2008-10
dc.identifier.urnurn:nbn:de:101:1-20080627301
dc.identifier.ppn1647467721


Dateien zu dieser Ressource

Thumbnail

Das Dokument erscheint in:

Zur Kurzanzeige