Polynomial Approximation
Marc Demange, Vangélis Th. Paschos · 2014
At the heart of the approximate methods for Non-deterministic Polynomial-time hard (NP-hard) problems from nonprofit organisation (NPO) is polynomial approximation, which studies the extent to which polynomial algorithms can give absolute guarantees as to the quality of the solutions obtained. This chapter outlines this result, which uses the main ingredients of many approximation schemes, and thus constitutes a significant example for geometric problems. It proposes a complete approximation scheme for the Boolean knapsack problem. The chapter presents a result concerning the approximation of the set covering problem. At the end of the brief overview of the domain of polynomial approximation algorithms, the chapter concludes by recalling the two principal issues in this domain, and makes some comments on the different types of results that it produces.