Intractability of approximate multi-dimensional nonlinear optimization on independence systems

DOI10.1016/J.DISC.2011.01.029MaRDI QIDQ533792zbMATH OpenOpenAlexFDO

Authors Jon Lee, Shmuel Onn, Robert Weismantel

Publication date 6 May 2011

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.5056

zbMATH Keywords

inapproximabilitynonlinear discrete optimizationErdős-Ko-Rado

Mathematics Subject Classification ID

Nonlinear programming (90C30) Integer programming (90C10)

Abstract: 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 ErdH{o}s-Ko-Rado theorem of Frankl, we show that for $d=2$, finding a $hon$-best solution requires exponential time.

Recommendations

• Approximate nonlinear optimization over weighted independence systems
• Publication:3033323
• Nonlinear Optimization over a Weighted Independence System
• The complexity of approximating a nonlinear program
• Non-approximability results for optimization problems on bounded degree instances
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Nondegeneracy and Quantitative Stability of Parameterized Optimization Problems with Multiple Solutions
• On Independence and Capacity of Multidimensional Semiconstrained Systems
• On the complexity of nonlinear mixed-integer optimization
• An inexact algorithm for composite nondifferentiable optimization

Cites work

• An Erdös-Ko-Rado theorem for direct products
• Approximate nonlinear optimization over weighted independence systems
• Nonlinear Matroid Optimization and Experimental Design
• Nonlinear discrete optimization. An algorithmic theory
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• The complexity of restricted spanning tree problems

Cited in

(4)

• Nonlinear Optimization over a Weighted Independence System
• On Independence and Capacity of Multidimensional Semiconstrained Systems
• Approximation Schemes for Multi-Budgeted Independence Systems
• Approximate nonlinear optimization over weighted independence systems

This page was built for publication: Intractability of approximate multi-dimensional nonlinear optimization on independence systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533792)