On a class of binary non-linear programming problems: Computational complexity & Approximation algorithms.
Báo cáo viên: Nguyễn Trung Thành (Đại học Phenikaa)
Thời gian: 9h, Thứ tư ngày 03.03.2021
Hình thức: online tại https://meet.google.com/weo-aihx-rbx

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, lp-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.