Complexity and Approximability of Committee Polyhedral Separability of Sets in General Position

Article type: Research Article

Authors: Khachay, Michael | Poberii, Maria

Affiliations: Institute of Mathematics and Mechanics, Ural Branch of Russian Academy of Sciences, S.Kovalevskoy 16, 620219 Ekaterinburg, Russia, e-mail: mkhachay@imm.uran.ru

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.

Keywords: polyhedral separability, computational complexity, approximation algorithms, committees

Journal: Informatica, vol. 20, no. 2, pp. 217-234, 2009