  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 Erd\H{o}s-Ko-Rado theorem of Frankl, we show that for $d=2$, finding a
$\rho n$-best solution requires exponential time.
