A PTAS for a class of binary non-linear programs with low-rank functions

Abstract

Binary non-linear programs belong to the class of which are computationally hard even to approximate. This paper aims to explore some conditions on the problem structure, under which the resulting problem can be well approximated. Particularly, we consider a setting when both objective function and constraint are low-rank functions, which depend only on a few of the input variables, and provide approximation schemes. Our result generalizes and unifies some existing results in the literature.