[HTML][HTML] Intractability of approximate multi-dimensional nonlinear optimization on independence systems
J Lee, S Onn, R Weismantel - Discrete mathematics, 2011 - Elsevier
J Lee, S Onn, R Weismantel
Discrete mathematics, 2011•ElsevierWe 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ős–Ko–Rado theorem of Frankl, we show that for d= 2, finding a ρn-
best solution requires exponential time.
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ős–Ko–Rado theorem of Frankl, we show that for d= 2, finding a ρn-
best solution requires exponential time.
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ős–Ko–Rado theorem of Frankl, we show that for d=2, finding a ρn-best solution requires exponential time.
Elsevier