Optimization Online


Nonlinear Optimization over a Weighted Independence System

Jon Lee (jonlee***at***us.ibm.com)
Shmuel Onn (onn***at***ie.technion.ac.il)
Robert Weismantel (weismant***at***math.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society