Nonlinear Optimization over a Weighted Independence System

Jon Lee (jonleeus.ibm.com)
Shmuel Onn (onnie.technion.ac.il)
Robert Weismantel (weismantmath.uni-magdeburg.de)

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.

Keywords: Frobenius number, independence system, nonlinear discrete optimization

Category 1: Combinatorial Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: IBM Research Report, RC24513

Download: [PDF]

Entry Submitted: 05/06/2008
Entry Accepted: 05/06/2008
Entry Last Modified: 05/16/2008

Modify/Update this entry