Computational and approximational complexity of combinatorial problems related to the committee polyhedral separability of finite sets / Khachai M.Yu. // Pattern Recognition and Image Analysis. - 2008. - V. 18, l. 2. - P. 236-242.

ISSN:

10546618

Type:

Article

Abstract:

In [1, 2], results on the computational and approximational complexity of a minimum affine separating committee (MASC) problem were obtained for finite sets A, B ⊂ ℚn . In particular, it was shown that this problem is NP-hard and does not belong to the class Apx (under the assumption 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 approximability threshold 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. © 2008 Pleiades Publishing, Ltd.

Author keywords:

Index keywords:

Computational methods; Finite difference method; Microfluidics; Set theory; Transients; (algorithmic) complexity; Combinatorial problems; Finite sets; Computational complexity

DOI:

10.1134/S1054661808020089

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-45149130377&doi=10.1134%2fS1054661808020089&partnerID=40&md5=8e2c660e91ec0974458048610d5695ce

Соавторы в МНС:

—

Другие поля

Поле	Значение
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-45149130377&doi=10.1134%2fS1054661808020089&partnerID=40&md5=8e2c660e91ec0974458048610d5695ce
Affiliations	Institute of Mathematics and Mechanics, Ural Division, Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg, 620219, Russian Federation
References	Khachai, M., Yu, On the Computational Complexity of Minimum Committee Problems and Related Problems (2006) Dokl. Akad. Nauk, 406, pp. 742-745. , 6; Yu. Khachai, M., On the computational and approximational complexity of the minimum affine separating committee problem (2006) Tavrich. Vestn. Inf. Mat., (1), pp. 34-43; Megiddo, N., Tamir, A., On the Complexity of Locating Linear Facilities in the Plane (1982) Oper. Res. Lett., 1, pp. 194-197. , 5; Megiddo, N., On the complexity of polyhedral separability (1988) Discrete Comput. Geom., (3), pp. 325-337; Blum, A.L., Rivest, R.L., Training a 3-Node Neural Network is NP-Complete (1992) Neural Networks, 5, pp. 117-127; Lin, J.H., Vitter, J.S., Complexity Results on Learning by Neural Nets (1991) Machine Learning, 6, pp. 211-230; Mazurov, V.D., Committees of systems of inequalities and the recognition problem (1971) Cybernetics, (3), pp. 140-146; Dinur, I., Regev, O., Smith, C., The hardness of 3-uniform hypergraph coloring (2002) Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, , November; Mazurov, V.D., Yu. Khachai, M., Rubin, A.I., Committee constructions for solving problems of selection, diagnostics and prediction (2002) Proc. Steklov Inst. Math., Suppl. 1, pp. S67-S101
Correspondence Address	Khachai, M. Yu.; Institute of Mathematics and Mechanics, Ural Division, Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg, 620219, Russian Federation; email: mkhachay@imm.uran.ru
Language of Original Document	English
Abbreviated Source Title	Pattern Recogn. Image Anal.
Source	Scopus