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
-best solution for nonlinear functions of the total weight of an independent set, where
is a constant depending on certain Frobenius numbers of the 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.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten