Complexity and Approximability of Committee Polyhedral Separability of Sets in General Position
Volume 20, Issue 2 (2009), pp. 217–234
Pub. online: 1 January 2009
Type: Research Article
Received
1 August 2008
1 August 2008
Accepted
1 May 2009
1 May 2009
Published
1 January 2009
1 January 2009
Abstract
It is known that the minimum affine separating committee (MASC) combinatorial optimization problem, which is related to some machine learning techniques, is NP-hard and does not belong to Apx class unless P=NP. In this paper, it is shown that the MASC problem formulated in a fixed dimension space within n>1 is intractable even if sets defining an instance of the problem are in general position. A new polynomial-time approximation algorithm for this modification of the MASC problem is presented. An approximation ratio and complexity bounds of the algorithm are obtained.