Nonlinear optimization over a weighted independence system

Loading...
Thumbnail Image
Date
2008
Volume
2008-10
Issue
Journal
Series Titel
Book Title
Publisher
Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach
Link to publishers version
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.

Description
Keywords
Citation
Lee, J., Onn, S., & Weismantel, R. (2008). Nonlinear optimization over a weighted independence system (Vol. 2008-10). Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach. https://doi.org//10.14760/OWP-2008-10
Collections
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.
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.