Nonlinear Optimization over a Weighted Independence System

  • Shmuel Onn
  • Robert Weismantel
  • Jon Lee
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , , Short URL: https://optimization-online.org/?p=10419

    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.

    Citation

    IBM Research Report, RC24513

    Article

    Download

    View Nonlinear Optimization over a Weighted Independence System