Full text of article: Russian language.
In papers [1, 2], results on the computational and approximational complexity of a minimum affine separating committee (MASC) problem are obtained for finite sets A, B ⊂ Q n. In particular, it is shown that this problem is NP-hard and does not belong to the class Apx (under the assumption approximability threshold 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 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 , is polynomially reducible to the problem under consideration. The method of reduction represents a modification of the method that was described in  and was used there for proving the hardness of problems on piecewise linear separability of finite sets on the plane.
combinatorial problems, committee polyhedral separability, computational and approximational.
Khachai MYu. Computational complexity and approximability of combinatorial problems related to the committee polyhedral separability of finite sets [In Russian]. Computer Optics 2007; 31(3): 63-69.
© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: email@example.com ; тел: +7 (846) 332-56-22, факс: +7 (846 2) 332-56-20