Computational complexity of the minimal committee problem and adjacent problems / Khachai M.Yu. // Pattern Recognition and Image Analysis. - 2006. - V. 16, l. 4. - P. 700-710.

ISSN:

10546618

Type:

Conference Paper

Abstract:

The computational complexity of two important special cases of the minimal committee problem (MC), viz., the problem on the minimal committee of finite sets (MCFS) and the problem on the minimal committee of a system of linear algebraic inequalities (MCLE), is studied. Both problems are shown to be NP-hard. Separately, some adjacent problems of integer optimization are shown to be intractable. The efficient approximability threshold is estimated for the MCFS problem, the estimates being allied to the results known for the set cover problem. The intractable and polynomially solvable subclasses of the MCLE problem are given. The problem of the minimal affine separation committee (MASC) is considered in conclusion; the results obtained earlier for the MCLE problem are shown to be valid for this problem as well. © Nauka/Interperiodica 2006.

Author keywords:

Index keywords:

нет данных

DOI:

10.1134/S1054661806040195

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-33845301693&doi=10.1134%2fS1054661806040195&partnerID=40&md5=d6022d374f74fcbf5a026ef206967734

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

—

Другие поля

Поле	Значение
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-33845301693&doi=10.1134%2fS1054661806040195&partnerID=40&md5=d6022d374f74fcbf5a026ef206967734
Affiliations	Institute of Mathematics and Mechanics, Ural Division, Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg, 620219, Russian Federation
References	Eremin, I.I., (2002) Theory of Linear Optimization, , BMV; Mazurov, V.D., Khachai, M.Yu., Rybin, A.I., Committee constructions for solving problems of selection, diagnostics, and prediction (2002) Proc. of the Steklov Institute of Mathematics, (SUPPL. 1), pp. 67-101; Mazurov, V.D., (1990) Committee Method in Optimization and Classification Problems, , (Nauka, Moscow), [in Russian]; Yeremin, I.I., Mazurov, V.D., (1979) Nonstationary Processes of Mathematical Programming, , (Nauka, Moscow), [in Russian]; Garey, M., Johnson, D.S., (1979) Computer and Intractability: A Guide to the Theory of NP-completeness, , (W.H. Freeman), San Francisco; Khachai, M.Yu., Rybin, A.I., On the committee solution with minimal number of terms of system of linear inequalities (1998) Proc. of XI Int. Baikal School-Seminar on Optimization Methods and Their Applications, pp. 26-40. , ISE of SD RAS, Irkutsk; Lund, C., Yannakakis, M., On the hardness of approximationg minimization problems (1992) Proc. of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 960-981; Feige, U., A threshold of ln n for approximating set cover (1998) J. of the ACM, 45 (4); Johnson, D.S., Approximation algorithms for combinatorial problems (1974) J. Computer and System Sci., 9 (3), pp. 256-278; Khachay, M.Yu., On computational complexity of the minimal committee of finite sets problem (2004) Proc. of the 2nd Int. Workshop on Discrete Optimization Methods in Production and Logistics, Omsk-irkutsk, pp. 176-179; Johnson, D.S., Preparata, F.P., The densest hemisphere problem (1978) Theoretical Computer Sci., 6, pp. 93-107; Dinur, I., Regev, O., Smyth, C., The hardness of 3-uniform hypergraph coloring (2002) Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, , November; Khachay, M.Yu., On approximate algorithm of a minimal committee of a linear inequalities system (2003) Pattern Recognition and Image Analysis, 13 (3), pp. 459-464; Mazurov, V.D., Committees of systems of inequalities and recognition problem (1971) Kibernetika No. 3, pp. 140-146
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