Laszlo Ladanyi, Jon Lee, et al.
Annals of Operations Research
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.
Laszlo Ladanyi, Jon Lee, et al.
Annals of Operations Research
Jon Lee
J Combin Optim
Jon Lee, Janny Leung
INFOR
Brenda L. Dietrich, Jon Lee, et al.
Annals of Operations Research