Computational complexity and approximability of combinatorial optimization problems connected with committee polyhedral separability of finite sets / Khachay M.Yu., Pobery M.I. // 20th International Conference EURO Mini Conference "Continuous Optimization and Knowledge-Based Technologies", EurOPT 2008. - 2008. - V. , l. . - P. 42-47.

ISSN:

нет данных

Type:

Conference Paper

Abstract:

The paper presents new results on computational complexity and approximability of the known minimum affine separating committee ( MASC) combinatorial optimization problem that is closely connected with the problem of optimal learning for perceptrons. It is known that the MASC problem is NP- hard and does not belong to Apx class unless P = NP . But the question whether this problem being formulated in feature space of the fixed dimensionality is NP- hard as well or it has a polynomial-time algorithms in this case, was still open (it is known, that the MASC problem in 1-dimensional space belongs to P). In this paper the intractability of the MASC problem in n- dimensional space within fixed n > 1 is proven. Actually, it is proven that the MASC being formulated in fixed-dimensional feature space is intractable even if the sets A and B using in its setting being in a general position. Separately new approximation threshold for the problem is obtained. © Institute of Mathematics and Informatics 2008.

Author keywords:

Approximability; Committees; Computational complexity; Polyhedral separability

Index keywords:

Algorithms; Combinatorial optimization; Knowledge based systems; Optimization; Approximability; Combinatorial optimization problems; Committees; Feature space; N-dimensional space; New results; Polyhe

DOI:

нет данных

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-84910150989&partnerID=40&md5=d219c1f911769d86c6439974aaf2aaeb

Соавторы в МНС:

—

Другие поля

Поле	Значение
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-84910150989&partnerID=40&md5=d219c1f911769d86c6439974aaf2aaeb
Affiliations	Institute of Mathematics and Mechanics, Ural Branch of RAS, S. Kovalevskoy, 16, Ekaterinburg, Russian Federation
Author Keywords	Approximability; Committees; Computational complexity; Polyhedral separability
Funding Details	RFBR, Russian Foundation for Basic Research
References	Judd, J.S., Complexity of connectionist learning with various node functions (1987) COINS Technical Report. No. 87-60, , University of Massachusetts; Judd, J.S., On the complexity of loading of shallow neural networks (1988) Journal of Complexity, 4, pp. 188-192; Lin, J.H., Vitter, J.S., Complexity results on learning by neural nets (1991) Machine Learning, 6, pp. 211-230; Blum, A.L., Rivest, R.L., Training a 3-Node neural network is np-complete (1992) Neural Networks, 5, pp. 117-127; Khachai M.Yu., Computational complexity of the minimum committee problem and related problems (2006) Doklady Mathematics, 73 (1), pp. 138-141; Mazurov, V.D., Committees of inequalities systems and the pattern recognition problem (1971) Kibernetika, 3, pp. 140-146; Megiddo, N., Tamir, A., On the complexity of locating linear facilities on the plane (1982) Operations Research Letters, 1 (5), pp. 194-197; Megiddo, N., On the complexity of polyhedral separability (1988) Discrete and Computational Geometry, 3, pp. 325-337
Correspondence Address	Khachay, M.Yu.; Institute of Mathematics and Mechanics, Ural Branch of RAS, S. Kovalevskoy, 16, Russian Federation
Editors	Sakalauskas L.Weber G.-W.Zavadskas E.
Publisher	Vilnius Gediminas Technical University
Conference name	20th International Conference EURO Mini Conference: Continuous Optimization and Knowledge-Based Technologies, EurOPT 2008
Conference date	20 May 2008 through 23 May 2008
Conference code	114738
ISBN	9789955282839
Language of Original Document	English
Abbreviated Source Title	Int. Conf. EURO Mini Conf.
Source	Scopus