Y. Berstein, Jon Lee, et al.
Mathematical Programming
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.
Y. Berstein, Jon Lee, et al.
Mathematical Programming
Jon Lee, Shmuel Onn, et al.
Operations Research Letters
Jon Lee, Shmuel Onn, et al.
Discrete Mathematics
Y. Berstein, Jon Lee, et al.
Mathematical Programming