General approximation algorithms for some arithmetical combinatorial problems

A general approximation technique for a large class of NP-hard optimization problems which involve arithmetic calculations is given. This technique guarantees a worst case relative error smaller than ε in time which is polynomial both in the size of the problem instance and 1/ε. It is also shown that problems in that class which are not approximable by this technique are not approximable in polynomial time at all, provided P ≠ NP, and hence this technique is the most general approximation technique applicable to this class.

Authors

• Shlomo Moran

Keywords

No keywords are indexed for this paper.