Publication
SIAM Journal on Discrete Mathematics
Paper

Approximate nonlinear optimization over weighted independence systems

View publication

Abstract

We consider optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide an efficient algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r depends only 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. © 2009 Society for Industrial and Applied Mathematics.

Date

Publication

SIAM Journal on Discrete Mathematics

Authors

Share