Член-корреспондент РАН с 02.06.2022 по Отделению математических наук.

Научные_интересы:
Хачай М.Ю. - известный специалист в области дискретной математики, теории сложности и вычислительной геометрии.
Основные направления исследований — вопросы вычислительной сложности и эффективной аппроксимируемости в классе алгоритмов с гарантированными оценками точности для труднорешаемых комбинаторных задач, в том числе, индуцированных процедурами статистического обучения. Построена теория вычислительной сложности комбинаторных задач, описывающих оптимальные процедуры обучении в классе мажоритарных кусочно-линейных решающих правил, найдены пороги полиномиальной аппроксимируемости и обоснованы полиномиальные приближенные алгоритмы с рекордными гарантированными оценками для этих задач. Получен ряд прорывных результатов в области эффективной аппроксимируемости для актуальных постановок классических маршрутных задач комбинаторной оптимизации, в том числе, в метрических пространствах произвольной фиксированной размерности удвоения.

Web_of_Science_ResearcherID: H-3251-2013
Ссылка_Web_of_Science: https://publons.com/researcher/1311223/michael-khachay/
Scopus_Author_ID: 6507117765
Ссылка_Scopus: https://www.scopus.com/authid/detail.uri?authorId=6507117765
РИНЦ_Author_ID: 14254
Ссылка_РИНЦ: https://www.elibrary.ru/author_profile.asp?id=14254
ORCID_ID: 0000-0003-3555-0080
Ссылка_ORCID: https://orcid.org/ 0000-0003-3555-0080

Научные_публикации:
1: Michael Khachay, Yuri Ogorodnikov, and Daniel Khachay: Efficient approximation of the metric CVRP in spaces of fixed doubling dimension. Journal of Global Optimization. 2021. 80(3): 679-710, DOI: 10.1007/s10898-020-00990-0
2: Michael Khachay and Katherine Neznakhina: Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters. Annals of Mathematics and Artificial Intelligence. 2020. 88, p. 53–69. DOI: 10.1007/s10472-019-09626-w
3: Michael Khachay and Daniel Khachay: Attainable accuracy guarantee for the k-medians clustering in [0, 1]. Optimization letters. 13, 1837–1853 (2019). DOI: 10.1007/s11590-018-1305-3
4: Khachai, M.Yu., Dubinin, R.D.: Approximability of the Vehicle Routing Problem in Finite-Dimensional Euclidean Spaces. Proceedings of the Steklov Institute of Mathematics. 2017. 297 (suppl. 1). P. 117-128. DOI: 10.1134/S0081543817050133
5: Chentsov, A. G., Khachai, M. Yu., Khachai, D. M.: An Exact Algorithm with Linear Complexity for a Problem of Visiting Megalopolises. Proceedings of the Steklov Institute of Mathematics. 2017. 295 (1). P. 38-46. DOI: 10.1134/S0081543816090054
6: Michael Khachay and Katherine Neznakhina: Approximability of the minimum-weight k-size cycle cover problem. Journal of Global Optimization. 2016. 66(1). P. 65-82. DOI: 10.1007/s10898-015-0391-3
7: Mikhail Khachay, Katherine Neznakhina: A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph. Proceedings of the Steklov Institute of Mathematics 06/2015; 289(1):111-125. DOI:10.1134/S0081543815050107
8: Michael Khachay: Committee polyhedral separability: complexity and polynomial approximation. Machine Learning. 2015; 101(1): 231-251. DOI:10.1007/s10994-015-5505-0
9: Mikhail Khachay, Maria Pobery, Daniel Khachay: Integer Partition Problem: Theoretical Approach to Improving Accuracy of Classifier Ensembles. International Journal of Artificial Intelligence 2015; 13(1): 135-146.
10: Mikhail Khachay, Helen Zaytseva: Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem. LNCS. Springer. 2015. Vol. 9486: 178-190

Премия_награда_год_присуждения:
1: Премия им. акад. А.И.Субботина, 2006