Constraint elimination method for the committee problem

We introduce a method of reducing the $q$-Member $p$-Committee Problem for an arbitrary finite system of sets to the same problem for a system of sets of smaller size and with a smaller number of subsystems with nonempty intersection maximal with respect to inclusion. For $p=\frac12$, for an infeasible system of linear inequalities in $\mathbb R^n$ we give an efficient implementation of this method with complexity polynomial in the number of inequalities and the number of committee elements, but exponential in the dimension of the space. For this implementation, we give experimental results for $n=2,3$.

Presented by the member of Editorial Board: A. I. Kibzun