The talk is aimed at describing various techniques used for designing fully-polynomial approximation schemes (FPTAS) for problems of minimizing and maximizing non-linear non-separable functions of Boolean variables, either with no additional constraints or with linear knapsack constraints. Most of the reported results are on optimizing a special quadratic function known as the half-product, which has numerous scheduling applications. Besides, problems with a more general objective and nested linear constraints are considered and a design of an FPTAS based on the K-approximation calculus is discussed.
展开▼
