On the computational complexity of the minimum committee problem / Khachay M.Yu. // Journal of Mathematical Modelling and Algorithms. - 2007. - V. 6, l. 4. - P. 547-561.

ISSN:
15701166
Type:
Article
Abstract:
Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67-101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NPTIME(n O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1-ε)ln (m-1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634-652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem. © 2007 Springer Science + Business Media B.V.
Author keywords:
Approximation algorithms; Computational complexity; Graph 3-colorability problem; Minimum committee problem; NP-completeness; Set cover problem
Index keywords:
нет данных
DOI:
10.1007/s10852-006-9056-z
Смотреть в Scopus:
https://www.scopus.com/inward/record.uri?eid=2-s2.0-36549032254&doi=10.1007%2fs10852-006-9056-z&partnerID=40&md5=3f697aa69e4344e3150a1bc5422e1e31
Соавторы в МНС:
Другие поля
Поле Значение
Link https://www.scopus.com/inward/record.uri?eid=2-s2.0-36549032254&doi=10.1007%2fs10852-006-9056-z&partnerID=40&md5=3f697aa69e4344e3150a1bc5422e1e31
Affiliations Institute of Mathematics and Mechanics, Russian Academy of Sciences, Ural Branch, S.Kovalevskoj 16, 620219 Ekaterinburg, Russian Federation
Author Keywords Approximation algorithms; Computational complexity; Graph 3-colorability problem; Minimum committee problem; NP-completeness; Set cover problem
References Mazurov, Vl.D., Khachai, M.Yu., Rybin, A.I., Committee constructions for solving problems of selection, diagnostics and prediction (2002) Proc. Steklov Inst. Math., 1, pp. 67-101; Feige, U., A threshold of ln n for approximating set cover (1998) J. ACM, 45, pp. 634-652. , 4; Arrow, K.J., (1963) Social Choice and Individual Values, , 2 Wiley New York; Saari, D.G., (1995) Basic Geometry of Voting., , Springer Berlin Heidelberg New York; Black, D., (1998) The Theory of Committees and Elections, , 2 Kluwer New York; Vapnik, V.N., (1998) Statistical Learning Theory, , Wiley New York; Hastie, T., Tibshirani, R., Friedman, J., (2001) Elements of Statistical Learning, , Springer Berlin Heidelberg New York; Eremin, I.I., (2002) Theory of Linear Optimization, , BVM, Offenbach; Eremin, I.I., Mazurov, Vl.D., (1979) Nonstable Processes of Mathematical Programming, , Nauka, Moscow; Lund, C., Yannakakis, M., On the hardness of approximating minimization problems (1992) Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 960-981. , IEEE Computer Society, New York; Johnson, D.S., Preparata, F.P., The densest hemisphere problem (1978) Theor. Comp. Sci., 6, pp. 93-107; Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , Freeman San Francisco, CA; Khachay, M.Yu., On approximate algorithm of a minimum committee of a linear inequalities system (2003) Pattern Recognit. Image Anal., 13, pp. 459-464. , 3; Gale, D., Kuhn, H.W., Tucker, A.W., Neighboring vertices on a convex polyhedron (1956) Linear Inequalities and Related Systems, pp. 255-263. , Princeton University Press Princeton, NJ
Correspondence Address Khachay, M.Yu.; Institute of Mathematics and Mechanics, Russian Academy of Sciences, Ural Branch, S.Kovalevskoj 16, 620219 Ekaterinburg, Russian Federation; email: mkhachay@imm.uran.ru
Language of Original Document English
Abbreviated Source Title J. Math. Model. Algorithms
Source Scopus