Hoạt động trong tuần

Tóm tắt: Binary non-linear programs (BNLP) naturally generalizes binary linear programs, which belong to the class of combinatorial NP-hard problems, meaning that exact polynomial-time algorithms are very unlikely to exist. It is therefore concerned with approximation algorithms that runs in polynomial time and returns a near-optimal solution, whose value is theoretically guaranteed to be within a small factor of the optimum. In this talk we will discuss the approximability of BNLP, with a focus on a class of low-rank objective functions and constraints. The low-rank functions subsume many well-studied non-linear functions as special cases, such as: polynomials, piecewise functions, l_p-norm functions, and sum-of-ratios functions. By following the convex and linear programming approaches, combined with the enumeration technique, we show that one can propose a general framework for designing polynomial-time approximation scheme (PTAS) for the studied problems. This result significantly generalizes and unifies some state-of-the-art results in the literature. We also highlight interesting directions for future work.