Computational complexity of the minimum committee problem and related problems / Khachai M.Yu. // Doklady Mathematics. - 2006. - V. 73, l. 1. - P. 138-141.

ISSN:

10645624

Type:

Article

Abstract:

Computational complexity of the minimum committees problem is determined. Theorems related to minimum committee of finite sets (MCFS) and minimum committee of a system of linear inequalities (MCLE) are proved. The technique used to reduce the set cover problem to the minimum committee problem can be used to solve the problem of Committee separation of sets. The algorithm in the class of uniformly distributed inequality system implies that the MCLE problem is polynomially solvable.

Author keywords:

Index keywords:

Polynomials; Problem solving; Set theory; Distributed inequality systems; Finite sets; Linear inequalities; Minimum committee of finite sets (MCFS); Computational complexity

DOI:

10.1134/S1064562406010376

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-33645990943&doi=10.1134%2fS1064562406010376&partnerID=40&md5=446c4f64b71e2237b09a6f29f098b8d2

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

—

Другие поля

Поле	Значение
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-33645990943&doi=10.1134%2fS1064562406010376&partnerID=40&md5=446c4f64b71e2237b09a6f29f098b8d2
Affiliations	Institute of Mathematics and Mechanics, Ural Division, Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg, 620219, Russian Federation
References	Khachai, M.Yu., Mazurov, Vl.D., Rybin, A.I., (2002) Proc. Steklov Inst. Math. Suppl., 1, pp. S67-S101; Mazurov, Vl.D., (1990) Committee Method in Optimization and Classification Problems, , (Nauka, Moscow) [in Russian]; Eremin, I.I., Mazurov, Vl.D., (1979) Nonstationary Processes in Mathematical Programming, , (Nauka, Moscow) [in Russian]; Khachai, M.Yu., Rybin, A.I., (1998) Proceedings of XI International Baikal School-seminar on Optimization Methods and Applications, pp. 26-40. , ISE SO RAN, Irkutsk; Khachay, M.Yu., (2004) Proceedings of 2nd International Workshop 'Discrete Optimization Methods in Production and Logistics', pp. 176-179. , Omsk; Lund, C., Yannakakis, M., (1992) Proceedings of XXXIII IEEE Symposium on Foundations of Computer Science, pp. 960-981. , IEEE Comput. Soc., New York; Feige, U., A threshold of inn for approximating set cover (1998) J. ACM, 45 (4); Johnson, D.S., Preparata, F.P., (1978) Theor. Comput. Sci., 6, pp. 93-107; Garey, M.R., Johnson, D., (1979) Computers and Intractability, , Freeman, San Francisco; Mir, Moscow; Khachay, M.Yu., (2003) Pattern Recogn. Image Anal., 13, pp. 459-464; Mazurov, Vl.D., (1971) Kibernetika, 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	Dokl. Math.
Source	Scopus