Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648550 | Discrete Mathematics | 2011 | 4 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jon Lee, Shmuel Onn, Robert Weismantel,