APPROXIMATION ALGORITHM AND APPLICATION FOR A NP-HARD PROBLEM SOLVING

Abstract

In this paper, we introduce some NP-hard problems and present an approximation algorithm to find a cluster (subset) of the largest cardinality and subset of points of a given cardinality. There is a radically different way of dealing with difficult optimization prob-lems: solve them approximately by a fast algorithm. This approach is particularly appealing for applications where a good but not necessarily optimal solution will suffice. Besides, in real-life applications, we often have to operate with inaccurate data to begin. Under such circumstances, going for an approximate solution can be a particularly sensible choice. Algorithm that is given is a polynomial-time approximation algorithm. This algorithm finds a feasible solution to problems when we consider the problem of searching a subset in a finite set of points of Euclidean space.