Nonlinear Optimization over a Weighted Independence System

DOI10.1007/978-3-642-02158-9_22MaRDI QIDQ3638454zbMATH OpenOpenAlexFDO

Authors Jon Lee, Shmuel Onn, Robert Weismantel

Publication date 2 July 2009

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmcombinatorial optimizationexponential running timeFrobenius numberindependence systeminteger programmingmatroidnonlinear optimizationoracle computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30)

Abstract: We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual weights and is independent of the size of the ground set. In contrast, we show that finding an optimal (0-best) solution requires exponential time even in a very special case of the problem.

Recommendations

• Approximate nonlinear optimization over weighted independence systems
• Approximate separable multichoice optimization over monotone systems
• Intractability of approximate multi-dimensional nonlinear optimization on independence systems
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• Nonlinear Matroid Optimization and Experimental Design

Cites work

• Matching is as easy as matrix inversion
• Nonlinear bipartite matching
• Nonlinear Matroid Optimization and Experimental Design
• On a Problem of Partitions

Cited in

(4)

• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• Approximate nonlinear optimization over weighted independence systems
• Nonlinear Matroid Optimization and Experimental Design
• Intractability of approximate multi-dimensional nonlinear optimization on independence systems

This page was built for publication: Nonlinear Optimization over a Weighted Independence System

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