Jon Lee, Shmuel Onn, et al.
Discrete Mathematics
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.
Discrete Mathematics
Jon Lee, Shmuel Onn, et al.
Discrete Mathematics
Jon Lee, Maxim Sviridenko, et al.
STOC 2010
Vijay S. Iyengar, Jon Lee, et al.
ACM Conference on Electronic Commerce 2001