Institute of Mathematics and Mechanics, Ural Branch of the RAS, Ekaterinburg, Russia

Full text of article: Russian language.

Abstract:
In papers [1, 2], results on the computational and approximational complexity of a minimum affine separating committee (MASC) problem are obtained for finite sets A, B ⊂ Q n. In particular, it is shown that this problem is NP-hard and does not belong to the class Apx (under the assumption approximability threshold that P ≠ NP). Nevertheless, questions concerning the bounds for its effective approximability threshold and for the computational complexity of a number of practically important particular cases of the problem obtained by imposing additional constraints, for example, by fixing the dimension of the space, remained open. In this paper, a lower bound is presented for the polynomial of the problem in the general case, and the intractability of the problem in spaces of fixed dimension greater than unity is proved. In particular, it is shown that the problem of committee separability remains hard even when it is formulated on the plane (i.e., in the simplest non-trivial case). This result follows from the fact that the well-known PC problem on covering a finite planar set by straight lines, whose hardness was proved in [3], is polynomially reducible to the problem under consideration. The method of reduction represents a modification of the method that was described in [4] and was used there for proving the hardness of problems on piecewise linear separability of finite sets on the plane.

Key words:
combinatorial problems, committee polyhedral separability, computational and approximational.

Citation:
Khachai MYu. Computational complexity and approximability of combinatorial problems related to the committee polyhedral separability of finite sets [In Russian]. Computer Optics 2007; 31(3): 63-69.

References:

1. Khachai MYu. On the computational complexity of the minimum committee problem and related problems [In Russian]. Proceedings of the Academy of Sciences of the USSR 2006; 406(6): 742-745.
   
2. Khachai MYu. On the computational and approximational complexity of the minimum affine separating committee problem [In Russian]. Tavricheskiy Herald of Informatics and Mathematics 2006; 1: 34–43.
   
3. Megiddo N, Tamir A. On the complexity of locating linear facilities in the plane. Operations research letters 1982; 1(5): 194-197.
   
4. Megiddo N. On the complexity of polyhedral separability. Discrete and Computational Geometry 1988; 3: 325-337.
   
5. Blum AL, Rivest RL. Training a 3-node Neural Network is NP-complete. Neural Networks 1992; 5: 117–127.
   
6. Lin JH, Vitter JS. Complexity Results on Learning by Neural Nets. Machine Learning 1991; 6: 211–230.
   
7. Mazurov VD. Committees of systems of inequalities and recognition problem [In Russian]. Kibernetika (Cybernetics) 1971; 3: 140–146.
   
8. Mazurov VlD, Khachai MYu, Rybin AI. Committee Constructions for Solving Problems of Selection. Diagnostics and Prediction. Proceedings of the Steklov Institute of mathematics 2002; 1: S67–S101.
   
9. Dinur I, Regev O, Smyth C. The hardness of 3- uniform hypergraph coloring. Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002.

---

© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 332-56-22, факс: +7 (846 2) 332-56-20