Conference paper
Q-Eval: Evaluating multiple attribute items using queries
Vijay S. Iyengar, Jon Lee, et al.
ACM Conference on Electronic Commerce 2001
We consider optimization of nonlinear objective functions that balance d linear criteria over n-element independence systems presented by linear-optimization oracles. For d=1, we have previously shown that an r-best approximate solution can be found in polynomial time. Here, using an extended ErdsKoRado theorem of Frankl, we show that for d=2, finding a ρn-best solution requires exponential time. © 2011 Elsevier B.V. All rights reserved.
Vijay S. Iyengar, Jon Lee, et al.
ACM Conference on Electronic Commerce 2001
Jon Lee, Shmuel Onn, et al.
SIAM Journal on Discrete Mathematics
Jon Lee
J Combin Optim
John Gunnels, Jon Lee, et al.
Mathematical Programming Computation