Geodesic
Combinatorial optimization problems related to the committee polyhedral separability of finite sets
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 14 (2008) no. 2, pp. 89-102 
V. D. Mazurov; M. Yu. Khachai; M. I. Poberii. Combinatorial optimization problems related to the committee polyhedral separability of finite sets. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 14 (2008) no. 2, pp. 89-102. http://geodesic.mathdoc.fr/item/TIMM_2008_14_2_a9/
@article{TIMM_2008_14_2_a9,
     author = {V. D. Mazurov and M. Yu. Khachai and M. I. Poberii},
     title = {Combinatorial optimization problems related to the committee polyhedral separability of finite sets},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {89--102},
     year = {2008},
     volume = {14},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2008_14_2_a9/}
}
TY  - JOUR
AU  - V. D. Mazurov
AU  - M. Yu. Khachai
AU  - M. I. Poberii
TI  - Combinatorial optimization problems related to the committee polyhedral separability of finite sets
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2008
SP  - 89
EP  - 102
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2008_14_2_a9/
LA  - ru
ID  - TIMM_2008_14_2_a9
ER  - 
%0 Journal Article
%A V. D. Mazurov
%A M. Yu. Khachai
%A M. I. Poberii
%T Combinatorial optimization problems related to the committee polyhedral separability of finite sets
%J Trudy Instituta matematiki i mehaniki
%D 2008
%P 89-102
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2008_14_2_a9/
%G ru
%F TIMM_2008_14_2_a9

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

In the paper, the computational and approximational complexity of the minimal affine separating committee problem, as well as of some important special cases of this problem, is investigated.

[1] Eremin I. I., Mazurov Vl. D., Nestatsionarnye protsessy matematicheskogo programmirovaniya, Nauka, M., 1979 | MR

[2] Eremin I. I., Sistemy lineinykh neravenstv i lineinaya optimizatsiya, UrO RAN, Ekaterinburg, 2007 | MR

[3] Rosenblatt F., “Analytic techniques for the study of neural nets”, IEEE Trans. on Appl. and Industry, 83:74 (1964), 285–292

[4] Blum A. L., Rivest R. L., “Training a 3-node neural network is NP-complete”, Neural Networks, 5 (1992), 117–127 | DOI | MR

[5] Lin J. H., Vitter J. S., “Complexity results on learning by neural nets”, Machine Learning, 6 (1991), 211–230

[6] Megiddo N., “On the complexity of polyhedral separability”, Discrete and Computational Geometry, 3 (1988), 325–337 | DOI | MR | Zbl

[7] Khachai M. Yu., “O vychislitelnoi slozhnosti zadachi o minimalnom komitete i smezhnykh zadach”, Dokl. RAN, 406:6 (2006), 742–745 | MR | Zbl

[8] Khachai M. Yu., “O vychislitelnoi i approksimatsionnoi slozhnosti zadachi o minimalnom affinnom razdelyayuschem komitete”, Tavricheskii vestnik informatiki i matematiki, 2006, no. 1, 34–43 | Zbl

[9] Mazurov Vl. D., “Komitety sistem neravenstv i zadacha raspoznavaniya”, Kibernetika, 1971, no. 3, 140–146 | MR | Zbl

[10] Dinur I., Regev O., Smyth C., The hardness of 3-uniform hypergraph coloring, Proc. of the 43rd Ann. IEEE symposium on foundations of computer science, Vancouver, 2002 | Zbl

[11] Mazurov Vl. D., Khachai M. Yu., Rybin A. I., “Committee constructions for solving problems of selection, diagnostics and prediction”, Proc. of the Steklov Inst. of Math., Suppl. 1, 2002, S67–S101 | MR

[12] Megiddo N., Tamir A., “On the complexity of locating linear facilities in the plane”, Operations Research Letters, 1:5 (1982), 194–197 | DOI | MR | Zbl