|
Avtomatika i Telemekhanika, 2012, Issue 2, Pages 163–177
(Mi at3619)
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers)
Integer Programming Problems
Constraint elimination method for the committee problem
K. S. Kobylkin Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, Yekaterinburg, Russia
Abstract:
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$.
Citation:
K. S. Kobylkin, “Constraint elimination method for the committee problem”, Avtomat. i Telemekh., 2012, no. 2, 163–177; Autom. Remote Control, 73:2 (2012), 355–368
Linking options:
https://www.mathnet.ru/eng/at3619 https://www.mathnet.ru/eng/at/y2012/i2/p163
|
Statistics & downloads: |
Abstract page: | 315 | Full-text PDF : | 67 | References: | 60 | First page: | 11 |
|