Intractability of approximate multi-dimensional nonlinear optimization on independence systems

DOI10.1016/J.DISC.2011.01.029zbMATH Open1218.90185arXiv1001.5056OpenAlexW1968366778MaRDI QIDQ533792FDOQ533792

Authors: Jon Lee, Shmuel Onn, Robert Weismantel 

Publication date: 6 May 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

inapproximability[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Ko-Rado&go=Go Erd��s-Ko-Rado]nonlinear discrete optimization

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Approximation Schemes for Multi-Budgeted Independence Systems
• Approximate nonlinear optimization over weighted independence systems
• Nonlinear Optimization over a Weighted Independence System
• On Independence and Capacity of Multidimensional Semiconstrained 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)