Известный специалист в области дискретной математики, теории сложности и вычислительной геометрии.

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

Научные интересы

Вопросы вычислительной сложности и эффективной аппроксимируемости в классе алгоритмов с гарантированными оценками точности для труднорешаемых комбинаторных задач, в том числе, индуцированных процедурами статистического обучения. 

Построена теория вычислительной сложности комбинаторных задач, описывающих оптимальные процедуры обучении в классе мажоритарных кусочно-линейных решающих правил, найдены пороги полиномиальной аппроксимируемости и обоснованы полиномиальные приближенные алгоритмы с рекордными гарантированными оценками для этих задач. 

Получен ряд прорывных результатов в области эффективной аппроксимируемости для актуальных постановок классических маршрутных задач комбинаторной оптимизации, в том числе, в метрических пространствах произвольной фиксированной размерности удвоения.

Научные публикации

• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• Michael Khachay: Committee polyhedral separability: complexity and polynomial approximation. Machine Learning. 2015; 101(1): 231-251. DOI:10.1007/s10994-015-5505-0.
• 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.
• Mikhail Khachay, Helen Zaytseva: Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem. LNCS. Springer. 2015. Vol. 9486: 178-190.

Премии и награды

Премия им. акад. А. И. Субботина, 2006 г.

Персональные профили исследователя

• Web of Science ResearcherID: H-3251-2013.
• Scopus Author ID: 6507117765.
• РИНЦ Author ID: 14254.
• ORCID ID: 0000-0003-3555-0080.