Jon Lee, Shmuel Onn, et al.
Operations Research Letters
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.
Jon Lee, Shmuel Onn, et al.
Operations Research Letters
Anureet Saxena, Pierre Bonami, et al.
Mathematical Programming
Pietro Belotti, Jon Lee, et al.
Optimization Methods and Software
John Gunnels, Jon Lee, et al.
Mathematical Programming Computation