Intractability of Approximate Multi-dimensional Nonlinear Optimization on Independence Systems

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 Erdos-Ko-Rado theorem of Frankl, we show that for d = 2, finding a -best solution requires exponential time.

By: Jon Lee; Shmuel Onn; Robert Weismantel

Published in: Discrete Mathematics, volume 311, (no 8-9), pages 780-3 in 2011

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .