Intractability of approximate multi-dimensional nonlinear optimization on independence systems

We consider optimization of nonlinear objective functions that balance dd linear criteria over nn-element independence systems presented by linear-optimization oracles. For d=1d=1, we have previously shown that an rr-best approximate solution can be found in polynomial time. Here, using an extended Erdős–Ko–Rado theorem of Frankl, we show that for d=2d=2, finding a ρnρn-best solution requires exponential time.