On the Computational Complexity of the Minimum Committee Problem |
| |
Authors: | Mikhail Yu Khachay |
| |
Institution: | (1) Institute of Mathematics and Mechanics, Russian Academy of Sciences, Ural Branch. S.Kovalevskoj 16, 620219 Ekaterinburg, Russia |
| |
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 NP⊂TIME(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.
|
| |
Keywords: | computational complexity NP-completeness set cover problem graph 3-colorability problem minimum committee problem approximation algorithms |
本文献已被 SpringerLink 等数据库收录! |
|