Jon Lee, Janny Leung, et al.
Discrete Optimization
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, Janny Leung, et al.
Discrete Optimization
Robert Hildebrand, Robert Weismantel, et al.
SODA 2017
Vijay S. Iyengar, Jon Lee, et al.
ACM Conference on Electronic Commerce 2001
Jon Lee, Shmuel Onn, et al.
Operations Research Letters