Persons
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
 
Khachay, Mikhail Yurevich
Corresponding member of RAS
Senior Researcher
Doctor of physico-mathematical sciences
E-mail:
Website: https://science.urfu.ru/ru/persons/михаил-юрьевич-хачай

https://www.mathnet.ru/eng/person28087
https://scholar.google.com/citations?user=uWkMwbQAAAAJ&hl=en
https://zbmath.org/authors/ai:khachai.m-yu
https://mathscinet.ams.org/mathscinet/MRAuthorID/627744
https://elibrary.ru/author_items.asp?spin=9243-1470
ISTINA https://istina.msu.ru/workers/60542810
https://orcid.org/0000-0003-3555-0080
https://www.webofscience.com/wos/author/record/H-3251-2013
https://www.scopus.com/authid/detail.url?authorId=6507117765
https://www.researchgate.net/profile/Michael_Khachay

Publications in Math-Net.Ru Citations
2024
1. Yu. Yu. Ogorodnikov, R. A. Rudakov, D. M. Khachai, M. Yu. Khachay, “Fault-tolerant families of production plans: mathematical model, computational complexity, and branch-and-bound algorithms”, Zh. Vychisl. Mat. Mat. Fiz., 64:6 (2024),  940–958  mathnet  elib; Comput. Math. Math. Phys., 64:6 (2024), 1193–1210
2023
2. E. D. Neznakhina, Yu. Yu. Ogorodnikov, K. V. Ryzhenko, M. Yu. Khachay, “Approximation algorithms with constant factors for a series of asymmetric routing problems”, Dokl. RAN. Math. Inf. Proc. Upr., 514:1 (2023),  89–97  mathnet  elib; Dokl. Math., 108:3 (2023), 499–505
3. M. Yu. Khachay, E. D. Neznakhina, K. V. Ryzhenko, “Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles”, Trudy Inst. Mat. i Mekh. UrO RAN, 29:3 (2023),  261–273  mathnet  mathscinet  elib; Proc. Steklov Inst. Math. (Suppl.), 323, suppl. 1 (2023), S121–S132  scopus 1
4. Ksenia  Ryzhenko, Katherine  Neznakhina, Michael  Khachay, “Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem”, Ural Math. J., 9:1 (2023),  135–146  mathnet  elib 4
2022
5. D. Yu. Turdakov, A. I. Avetisyan, K. V. Arkhipenko, A. V. Antsiferova, D. S. Vatolin, S. S. Volkov, A. V. Gasnikov, D. A. Devyatkin, M. D. Drobyshevskiy, A. P. Kovalenko, M. I. Krivonosov, N. V. Lukashevich, V. A. Malykh, S. I. Nikolenko, I. V. Oseledets, A. I. Perminov, I. V. Sochenkov, M. M. Tihomirov, A. N. Fedotov, M. Yu. Khachay, “Trusted artificial intelligence: challenges and promising solutions”, Dokl. RAN. Math. Inf. Proc. Upr., 508 (2022),  13–18  mathnet  elib; Dokl. Math., 106:suppl. 1 (2022), S9–S13 1
6. M. Yu. Khachay, E. D. Neznakhina, K. V. Ryzhenko, “Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem”, Trudy Inst. Mat. i Mekh. UrO RAN, 28:3 (2022),  241–258  mathnet  mathscinet  elib; Proc. Steklov Inst. Math. (Suppl.), 319, suppl. 1 (2022), S140–S155  isi  scopus 5
2021
7. Yu. Yu. Ogorodnikov, M. Yu. Khachay, “Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension”, Zh. Vychisl. Mat. Mat. Fiz., 61:7 (2021),  1206–1219  mathnet  elib; Comput. Math. Math. Phys., 61:7 (2021), 1194–1206  isi  scopus 1
2020
8. M. Yu. Khachay, Yu. Yu. Ogorodnikov, “Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension”, Dokl. RAN. Math. Inf. Proc. Upr., 493 (2020),  74–80  mathnet  zmath  elib; Dokl. Math., 102:1 (2020), 324–329 5
2019
9. M. Yu. Khachay, Yu. Yu. Ogorodnikov, “Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension”, Trudy Inst. Mat. i Mekh. UrO RAN, 25:4 (2019),  235–248  mathnet  elib 4
2018
10. M. Yu. Khachay, Yu. Yu. Ogorodnikov, “Polynomial time approximation scheme for the capacitated vehicle routing problem with time windows”, Trudy Inst. Mat. i Mekh. UrO RAN, 24:3 (2018),  233–246  mathnet  elib; Proc. Steklov Inst. Math. (Suppl.), 307, suppl. 1 (2019), S51–S63  isi 9
2017
11. M. Yu. Khachai, D. M. Khachai, V. S. Pankratov, “Attainable best guarantee for the accuracy of $k$-medians clustering in $[0,1]$”, Trudy Inst. Mat. i Mekh. UrO RAN, 23:4 (2017),  301–310  mathnet  elib
12. M. Yu. Khachay, E. D. Neznakhina, “Solvability of the Generalized Traveling Salesman Problem in the class of quasi- and pseudopyramidal tours”, Trudy Inst. Mat. i Mekh. UrO RAN, 23:3 (2017),  280–291  mathnet  elib
2016
13. M. Yu. Khachai, E. D. Neznakhina, “Approximation Schemes for the Generalized Traveling Salesman Problem”, Trudy Inst. Mat. i Mekh. UrO RAN, 22:3 (2016),  283–292  mathnet  mathscinet  elib; Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 97–105  isi  scopus 20
14. M. Yu. Khachai, R. D. Dubinin, “Approximability of the optimal routing problem in finite-dimensional Euclidean spaces”, Trudy Inst. Mat. i Mekh. UrO RAN, 22:2 (2016),  292–303  mathnet  mathscinet  elib; Proc. Steklov Inst. Math. (Suppl.), 297, suppl. 1 (2017), 117–128  isi  scopus 12
15. Daniel M. Khachai, Michael Yu. Khachay, “On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line”, Ural Math. J., 2:2 (2016),  117–126  mathnet  zmath  elib 1
2015
16. A. G. Chentsov, M. Yu. Khachai, M. Yu. Khachai, “An exact algorithm with linear complexity for a problem of visiting megalopolises”, Trudy Inst. Mat. i Mekh. UrO RAN, 21:3 (2015),  309–317  mathnet  mathscinet  elib; Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 38–46  isi  scopus 20
2014
17. M. Yu. Khachai, M. I. Poberii, “Scheme of boosting in the problems of combinatorial optimization induced by the collective training algorithms”, Avtomat. i Telemekh., 2014, no. 4,  81–93  mathnet; Autom. Remote Control, 75:4 (2014), 657–667  isi  scopus 2
18. M. Yu. Khachai, E. D. Neznakhina, “Polynomial-time approximation scheme for a Euclidean problem on a cycle covering of a graph”, Trudy Inst. Mat. i Mekh. UrO RAN, 20:4 (2014),  297–311  mathnet  mathscinet  elib; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 111–125  isi  scopus 11
19. E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph”, Trudy Inst. Mat. i Mekh. UrO RAN, 20:2 (2014),  99–112  mathnet  mathscinet  elib; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101  isi  scopus 3
2013
20. Vl. D. Mazurov, M. Yu. Khachai, “Boosting and the polynomial approximability of the problem on a minimum affine separating committee”, Trudy Inst. Mat. i Mekh. UrO RAN, 19:2 (2013),  231–236  mathnet  mathscinet  elib 3
21. I. I. Eremin, E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “$2$-approximate algorithm for finding a clique with minimum weight of vertices and edges”, Trudy Inst. Mat. i Mekh. UrO RAN, 19:2 (2013),  134–143  mathnet  mathscinet  elib; Proc. Steklov Inst. Math. (Suppl.), 284, suppl. 1 (2014), 87–95  isi  scopus 6
2012
22. E. G. Pytkeev, M. Yu. Khachai, “Topological properties of measurable structures and sufficient conditions for uniform convergence of frequencies to probabilities”, Avtomat. i Telemekh., 2012, no. 2,  89–98  mathnet; Autom. Remote Control, 73:2 (2012), 291–299  isi  scopus
23. M. Yu. Khachai, M. I. Poberii, “The computational complexity and approximability of a series of geometric covering problems”, Trudy Inst. Mat. i Mekh. UrO RAN, 18:3 (2012),  247–260  mathnet  elib; Proc. Steklov Inst. Math. (Suppl.), 283, suppl. 1 (2013), 64–77  isi  scopus 3
2010
24. M. Yu. Khachai, “Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules”, Avtomat. i Telemekh., 2010, no. 3,  178–189  mathnet  mathscinet  zmath; Autom. Remote Control, 71:3 (2010), 528–539  isi  scopus 4
25. M. Yu. Khachai, “Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning”, Trudy Inst. Mat. i Mekh. UrO RAN, 16:3 (2010),  276–284  mathnet  elib; Proc. Steklov Inst. Math. (Suppl.), 272, suppl. 1 (2011), S46–S54  isi  scopus 2
26. E. G. Pytkeev, M. Yu. Khachai, “Sigma-compactness of metric Boolean algebras and uniform convergence of frequencies to probabilities”, Trudy Inst. Mat. i Mekh. UrO RAN, 16:1 (2010),  127–139  mathnet  elib; Proc. Steklov Inst. Math. (Suppl.), 272, suppl. 1 (2011), S138–S151  isi  scopus 1
2008
27. V. D. Mazurov, M. Yu. Khachai, M. I. Poberii, “Combinatorial optimization problems related to the committee polyhedral separability of finite sets”, Trudy Inst. Mat. i Mekh. UrO RAN, 14:2 (2008),  89–102  mathnet  zmath  elib; Proc. Steklov Inst. Math. (Suppl.), 263, suppl. 2 (2008), S93–S107  isi  scopus 2
2007
28. V. D. Mazurov, M. Yu. Khachai, “Parallel computations and committee constructions”, Avtomat. i Telemekh., 2007, no. 5,  182–192  mathnet  mathscinet  zmath; Autom. Remote Control, 68:5 (2007), 912–921  scopus 7
2004
29. V. D. Mazurov, M. Yu. Khachai, “Committees of systems of linear inequalities”, Avtomat. i Telemekh., 2004, no. 2,  43–54  mathnet  mathscinet  zmath; Autom. Remote Control, 65:2 (2004), 193–203  isi  scopus 12
2003
30. V. D. Mazurov, M. Yu. Khachai, “Committee constructions as a generalization of contradictory problems of operations research”, Diskretn. Anal. Issled. Oper., Ser. 2, 10:2 (2003),  56–66  mathnet  mathscinet  zmath 1
2002
31. V. D. Mazurov, M. Yu. Khachai, A. I. Rybin, “Committee constructions for solving problems of selection, diagnostics, and prediction”, Trudy Inst. Mat. i Mekh. UrO RAN, 8:1 (2002),  66–102  mathnet  mathscinet  zmath  elib; Proc. Steklov Inst. Math. (Suppl.), 2002no. , suppl. 1, S67–S101 10
32. M. Yu. Khachai, “A game against nature associated with majority-vote decision making”, Zh. Vychisl. Mat. Mat. Fiz., 42:10 (2002),  1609–1616  mathnet  mathscinet  zmath; Comput. Math. Math. Phys., 42:10 (2002), 1547–1554 3
1997
33. M. Yu. Khachai, “On the existence of a majority committee”, Diskr. Mat., 9:3 (1997),  82–95  mathnet  mathscinet  zmath; Discrete Math. Appl., 7:4 (1997), 383–397 1
34. M. Yu. Khachaĭ, “Estimate of the number of members in the minimal committee of a system of linear inequalities”, Zh. Vychisl. Mat. Mat. Fiz., 37:11 (1997),  1399–1404  mathnet  mathscinet  zmath; Comput. Math. Math. Phys., 37:11 (1997), 1356–1361 2
2014
35. V. I. Berdyshev, V. V. Vasin, S. V. Matveev, A. A. Makhnev, Yu. N. Subbotin, N. N. Subbotina, V. N. Ushakov, M. Yu. Khachai, A. G. Chentsov, “Ivan Ivanovich Eremin”, Trudy Inst. Mat. i Mekh. UrO RAN, 20:2 (2014),  5–12  mathnet  mathscinet  elib; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 1–8  isi
36. Yu. G. Evtushenko, M. Yu. Khachai, “In memory of Ivan Ivanovich Eryomin (22.01.1933–21.07.2013)”, Zh. Vychisl. Mat. Mat. Fiz., 54:5 (2014),  887–891  mathnet  elib
2012
37. A. I. Kibzun, E. A. Nurminskii, M. Yu. Khachai, “Mathematical Programming: State of the Art”, Avtomat. i Telemekh., 2012, no. 2,  3–4  mathnet  elib

Presentations in Math-Net.Ru
1. Approximate algorithms with fixed approximation factors for asymmetric route problems of combinatorial optimization
M. Yu. Khachay
Scientific seminar on the differential and functional differential equations
June 4, 2024 12:00   
2. Алгоритмы с теоретическими гарантиями в задачах эффективной маршрутизации мобильных роботов
M. Yu. Khachay
General Meeting of the Branch of Mathematical Sciences, RAS, 2021
December 13, 2021   
3. Адаптивный эвристический солвер для обобщенной задачи коммивояжера с ограничениями предшествования
M. Yu. Khachay, Kudryavtsev A.V., A. A. Petunin
Seminar for Optimization Laboratory
October 23, 2020 11:00
4. Эффективная аппроксимируемость задачи маршрутизации транспорта в метрических пространствах фиксированной размерности удвоения
M. Yu. Khachay
Seminar for Optimization Laboratory
February 14, 2020 11:00
5. Эффективные алгоритмы с гарантированными оценками для маршрутных задач комбинаторной оптимизации
M. Yu. Khachay
IX Internet video conference "Day of Mathematics and Mechanics"
September 9, 2019 11:40   
6. Достижимая гарантия качества кластеризации методом k-медиан на отрезке [0,1]
M. Yu. Khachay
Seminar for Optimization Laboratory
October 13, 2017 12:00
7. Квазипирамидальные маршруты для обобщенной задачи коммивояжера
M. Yu. Khachay
Seminar for Optimization Laboratory
October 13, 2017 11:00
8. Аппроксимируемость задачи маршрутизации и близких задач в классе детерминированных алгоритмов
M. Yu. Khachay
Mathematical Workshop of the School of Applied Mathematics and Computer Science (MIPT)
April 28, 2017 18:30   
9. Эффективные алгоритмы для некоторых актуальных обобщений задачи коммивояжера
M. Yu. Khachai
Conference of Professors of the RAS in the Department of Mathematical Sciences of the Russian Academy of Sciences
June 14, 2016 11:45   
10. Approximation of the optimal routing problem for the finite-dimensional spaces
M. Yu. Khachai
Seminar of Control System Department
June 2, 2016 12:00
11. Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов
M. Yu. Khachai
Seminar for Optimization Laboratory
February 12, 2016 11:00
12. Методология решения комбинаторных задач о наименьшей системе представителей и родственных задач
M. Yu. Khachai
Seminar for Optimization Laboratory
November 6, 2015 11:00
13. Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem
M. Yu. Khachai
Seminar for Optimization Laboratory
October 30, 2015 11:00
14. Новые результаты в комбинаторной оптимизации типа задачи коммивояжера
M. Yu. Khachai
PreMoLab Seminar
October 15, 2014 17:00
15. Polynomial-time approximation scheme for problem of splitting complete Euclidean graph on two minimum weight gamiltonian cycles
M. Yu. Khachai, Neznakhina E.D.
Seminar for Optimization Laboratory
April 18, 2014 11:00

Organisations
 
  Contact us:
  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024