Approximate Nonlinear Optimization over Weighted Independence Systems | Zendy

Jon Lee | Zendy; Shmuel Onn | Zendy; Robert Weismantel | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Approximate Nonlinear Optimization over Weighted Independence Systems

Author(s) -

Jon Lee,

Shmuel Onn,

Robert Weismantel

Publication year - 2009

Publication title -

siam journal on discrete mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.843

H-Index - 66

eISSN - 1095-7146

pISSN - 0895-4801

DOI - 10.1137/080718103

Subject(s) - mathematics , independence (probability theory) , nonlinear system , combinatorics , independence number , mathematical optimization , discrete mathematics , algorithm , statistics , graph , physics , quantum mechanics

We consider optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide an efficient algorithm that determines an $r$-best solution for nonlinear functions of the total weight of an independent set, where $r$ depends only 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research