• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • The Mixed Chinese Postman Problem
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
June 5, 2026
Neural Network Maps as a Method for Constructing Mathematical Models
Scientists from HSE University–Nizhny Novgorod and the Institute of Physics Belgrade, Serbia, are jointly exploring the application of machine learning techniques and neural networks to the study of nonlinear dynamics. Natalya Stankevich, Leading Research Fellow at the Laboratory of Topological Methods in Dynamics of the Faculty of Informatics, Mathematics, and Computer Science at HSE University–Nizhny Novgorod, spoke to the HSE News Service about this international project.
June 5, 2026
‘In the Age of Technology, It Is Interesting to Look into the Past and Think about What We Can Take from It
Polina Tabakova decided to apply for a Philology degree at HSE in Nizhny Novgorod because she grew up in Mari El and did not want to move far away from the Russian forests. In an interview for the Young Scientists of HSE University project, she spoke about the genre of the campus novel, the existential drama of Kolobok, and a blackout version of Eugene Onegin.
June 5, 2026
HSE Scientists Develop Method to Compress Large Language Models Without Losing Quality
Researchers from the AI and Digital Science Institute at the HSE Faculty of Computer Science have developed a new compression method for large language models such as GPT and LLaMA that reduces their size by 25–36% without additional training or significant loss of accuracy. This is the first approach to use mathematical transformations—specifically, rotations of model weights—to make models more amenable to compression with structured matrices. The study results have been published in ACL Findings 2025. The code is available on GitHub.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

The Mixed Chinese Postman Problem

Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 107–122.
M.K. Gordenko, S.M. Avdoshin

The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which defined on mixed multigraph) using the reduction of the original problem into General Travelling Salesman Problem (GTSP). The variants of CPP are pointed out. The mathematical formulations of some problems are presented. The algorithm for reduction the MCPP in multigraph into GTSP is shown. The experimental results of solving MCPP in multigraph through the reduction into GTSP are presented. 

Research target: Mathematics Computer Science
Priority areas: IT and mathematics
Language: English
Full text
DOI
Text on another site
Keywords: задача коммивояжераTraveling Salesman Problemheuristic algorithmэвристический алгоритмMixed Chinese Postman ProblemArc Routing ProblemСмешанная задача китайского почтальонаЗадача маршрутизации дуг
Similar publications
Wave dynamics within the Whitham-Ostrovsky equation
Flamarion M. V., Pelinovsky E., Nonlinear Dynamics 2026 Vol. 114 Article 784
In this article, we investigate wave packet and solitary wave dynamics in the Whitham–Ostrovsky (WO) equation. By means of a multiple-scales expansion, we formally derive a nonlinear Schrödinger (NLS) equation governing the envelope evolution.The corresponding modulational stability diagram is then obtained using the Lighthill criterion. We show that sufficiently large values of the low-frequency dispersive term render ...
Added: June 5, 2026
On structural stability of 3-diffeomorphisms with the Smale solenoid attractor–repeller dynamics
Medvedev T. V., Pochinka O., Chaos 2026 Vol. 36 No. 6 Article 063107
We consider 3-diffeomorphisms with source–sink dynamics where Smale solenoids play the role of the source and the sink (NSSS-diffeomorphisms). It is known that such diffeomorphisms exist only on lens spaces. On the 3-sphere, every NSSS-diffeomorphism is associated with an exchangeable braid. An exchangeable braid with the strand number n was constructed for each n   3 in such a way ...
Added: June 4, 2026
Proceedings of the 43rd International Conference on Machine Learning (ICML 2026)
Seul: PMLR, 2026.
Added: June 4, 2026
A model exhibiting all possible types of hyperbolic chaos on the 2-torus
Kazakov A., Shilov O. M., Mints D. et al., Chaos 2026 Vol. 36 No. 6 Article 063112
We study hyperbolic chaotic dynamics for maps of a two-dimensional torus. We introduce a two-parameter family of diffeomorphisms which, as we show, demonstrates all types of hyperbolic chaotic dynamics that can appear in the two-dimensional case. In addition, we describe all the bifurcations responsible for the transitions between these chaotic regimes. ...
Added: June 4, 2026
Об эквивалентности по надстройке декартовых произведений регулярных гомеоморфизмов с гомеоморфизмами Данжуа
Nozdrinova E., Pochinka O., Shmukler V., Математический сборник 2026 Т. 217 № 6 С. 71–89
Гомеоморфизмы топологических пространств называются эквивалентными по надстройке, если надстройки над ними топологически эквивалентны. В частности, топологически сопряженные гомеоморфизмы эквивалентны по надстройке. Известно, что для гомологически неприводимых гомеоморфизмов их топологическая сопряженность является необходимым и достаточным условием их эквивалентности по надстройке. Тогда как инварианты топологической сопряженности гомологически приводимых гомеоморфизмов во многих случаях являются избыточными для эквивалентности по ...
Added: June 3, 2026
Случайные блуждания на симметрических пространствах некомпактного типа ранга 1
Gnetov F., Konakov V., Успехи математических наук 2026 Т. 81 № 3 (489) С. 161–162
Пусть M обозначает симметрическое пространство некомпактного типа ранга 1. Опираясь на фундаментальную работу [1], в [2] было показано, что плотность соответствующим образом нормированной суммы независимых Hn-значных случайных величин, определенная через сложение Мёбиуса в модели шара Пуанкаре, сходится к фундаментальному решению соответствующего уравнения теплопроводности. Пределом являлся нормальный закон на Hn, соответствующий ядру теплопроводности, определяемому оператором Лапласа–Бельтрами. ...
Added: June 2, 2026
OpenAtom Foundation. Консорциум, развивающий Open Source в Китае.
Silakov D., Системный администратор 2026 № 3 С. 28–33
В статье про платформы для разработки открытого ПО в Китае мы рассказали про GitCode – молодой проект, позиционируемый как площадка для разработчиков со всего мира. Сейчас на GitCode размещаются проекты, созданные в КНР, но некоторые из них уже известны и на международной арене. Помочь открытым проектам в становлении, развитии и расширению аудитории призван фонд OpenAtom ...
Added: June 2, 2026
The recognition-by-components method
Slivnitsin P., Mylnikov L., Engineering Applications of Artificial Intelligence 2026 Vol. 179 Article 115185
The paper describes a applied artificial intelligence task of recognition-by-components method of real objects based on the recognition of a limited set of primitives or components. The recognition-by-components makes it possible to determine the components, that compose an object, and increase the number of recognizable objects without degrading the recognition quality. Training is performed on ...
Added: May 29, 2026
Electrical networks and data analysis in phylogenetics
Gorbounov Vassily, Kazakov A., Data Analytics and Topology 2025 Vol. 1 No. 1 P. 33–45
A classic problem in data analysis is studying the systems of subsets defined by either a similarity or a dissimilarity function on X which is either observed directly or derived from a data set. For an electrical network there are two functions on the set of the nodes defined by the resistance matrix and the response ...
Added: May 28, 2026
Brain-Computer Interfaces for Gait Rehabilitation After Stroke A Scoping Review
Mokienko O., Zisman M. A., Bobrov P. et al., American Journal of Physical Medicine and Rehabilitation 2026 Vol. 105 No. 6 P. 555–563
Brain-computer interfaces (BCIs) represent a promising technology for restoring lower limb motor functions and gait after stroke. The application of BCIs in this field is supported by a limited number of studies. The objective of the review was to systematically and critically evaluate the current evidence on the use of BCIs for lower limb function ...
Added: May 28, 2026
Generalizing the Brady-Yong Algorithm: Efficient Fast Hough Transform for Arbitrary Image Sizes
Kazimirov D., Rybakova E., Vitalii V. Gulevskii et al., IEEE Access 2025 Vol. 13 P. 20101–20132
The Hough (discrete Radon) transform (HT/DRT) is a digital image processing tool that has become indispensable in many application areas, ranging from general image processing to neural networks and X-ray computed tomography. The utilization of the HT in applied problems demands its computational efficiency and increased accuracy. The de facto standard algorithm for the fast ...
Added: May 28, 2026
Universal Comparison Methodology for Hough Transform Approaches
Kazimirov D., Vitalii Gulevskii, Kroshnin A. et al., Mathematics 2026 Article 1136
The Hough transform (HT) is widely used in computer vision, tomography, and neural networks. Numerous algorithms for HT computation have been proposed, making their systematic comparison essential. However, existing comparative methodologies are either non-universal and limited to certain HT formulations, or task-oriented, relying on application-specific criteria that do not fully capture algorithmic properties. This paper ...
Added: May 28, 2026
ML-based Fast Simulation of FARICH Responses
Shipilov F., Barnyakov A., Ivanov A. et al., / Series Physics "arxiv.org". 2026.
A fast simulation of the detector response is a vital task in high-energy physics (HEP). Traditional Monte-Carlo methods form the backbone of modern particle physics simulation software but are computationally expensive. We present a machine-learning-based approach to fast simulation of the Focusing Aerogel Ring Imaging Cherenkov (FARICH) detector response. Given a particle track and momentum, ...
Added: May 19, 2026
Natural hazard database from Internet publications: text mining with a large language model
Derkacheva A., Sakirkina M., Kraev G. et al., /. 2026.
Comprehensive data on natural hazards and their consequences are crucial for effective for risk assessment, adaptation planning, and emergency response. However, many countries face challenges with fragmented, inconsistent, and inaccessible data, particularly regarding local-scale events. To address this data gap in Russia, we developed an end-to-end processing pipeline that scrapes news from various online sources, ...
Added: April 28, 2026
Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena
Pilé I., Deng Y., Shchur L., / Series arXiv "math". 2026. No. 2604.10254.
We investigate the spatial overlap of successive spin configurations in Markov chain Monte Carlo simulations using the local Metropolis algorithm and the Svendsen-Wang and Wolff cluster algorithms. We examine the dynamics of these algorithms for two models in different universality classes: the Ising model and the Potts model with three components. The overlap of two ...
Added: April 20, 2026
Using predefined vector systems to speed up neural network multimillion class classification
Gabdullin N., Androsov I., / Series Computer Science "arxiv.org". 2026.
Label prediction in neural networks (NNs) has O(n) complexity proportional to the number of classes. This holds true for classification using fully connected layers and cosine similarity with some set of class prototypes. In this paper we show that if NN latent space (LS) geometry is known and possesses specific properties, label prediction complexity can ...
Added: April 2, 2026
Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection
Sorokin K., Beketov M., Онучин А. et al., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.
Community detection in complex networks is a fundamental problem, open to new approaches in various scientific settings. We introduce a novel community detection method, based on Ricci flow on graphs. Our technique iteratively updates edge weights (their metric lengths) according to their (combinatorial) Foster version of Ricci curvature computed from effective resistance distance between the ...
Added: January 15, 2026
Implementing Transport Coding in OMNeT++ for Message Delay Reduction
Petrovanov I., Sergeev A., / Series Computer Science "arxiv.org". 2025. No. 2512.18332.
Transport coding reduces message delay in packet-switched networks by introducing controlled redundancy at the transport layer:  original packets are encoded into  coded packets, and the message is reconstructed after the first  successful deliveries, effectively shifting latency from the maximum packet delay to the -th order statistic. We present a concise, reproducible discrete-event implementation of transport coding in OMNeT++, including ...
Added: December 24, 2025
Hessian-based lightweight neural network for brain vessel segmentation on a minimal training dataset
Меньшиков И. А., Бернадотт А. К., Elvimov N. S., / Series arXie "Statistical mechanics". 2025.
Accurate segmentation of blood vessels in brain magnetic resonance angiography (MRA) is essential for successful surgical procedures, such as aneurysm repair or bypass surgery. Currently, annotation is primarily performed through manual segmentation or classical methods, such as the Frangi filter, which often lack sufficient accuracy. Neural networks have emerged as powerful tools for medical image ...
Added: December 1, 2025
Разработка алгоритма по раскраске графов на основе Эвристического и Жадного алгоритмов с применением элементов геймификации
Nazarovskiy E., Rustamkhanova G., Сборник материалов студенческой научно-практической конференции имени Льва Львовича Любимова 2023 С. 128–132
На настоящий день дискретная математика играет существенную роль в изучении высшей математики в вузах. Одной из основополагающих тем курса является теория графов, которая широко применяется при решении экономических и управленческих задач, в программировании и других областях. С помощью теории графов можно решить множество задач. Классическим примером такой задачи является раскраска графов. ...
Added: November 30, 2025
Determining the boundary of dynamical chaos in the generalized Chirikov map via machine learning
Chernyshov D., Satanin A., Shchur L., / Series arXiv "math". 2025.
We investigate the boundary separating regular and chaotic dynamics in the generalized Chirikov map, an extension of the standard map with phase-shifted secondary kicks. Lyapunov maps were computed across the parameter space (K,K(α, τ)) and used to train a convolutional neural network (ResNet18) for binary classification of dynamical regimes. The model reproduces the known critical ...
Added: November 21, 2025
Эффективный алгоритм торговли на фондовом рынке: ретроспективный анализ, основанный на данных по S&P-500.
Rubchinskiy A., Chubarova D., / Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2025. No. WP7/2025/01.
The article examines one of the most famous examples of socio-economic systems, characterized by significant uncertainty – the S&P-500 stock market, where shares of 500 largest US companies are traded. No assumptions are made about the probabilistic characteristics of the stock market. A flexible algorithm for daily trading has been developed, based on both known fixed data ...
Added: November 9, 2025
Интеграция метаэвристических алгоритмов решения несимметричной задачи коммивояжёра с методом ветвей и границ
Fomichev M., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47–54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Added: March 22, 2020
Коррeляция сложности и времени решения TSP
Головешкин В. А., Zhukova G., Ulyanov M. et al., Системы компьютерной математики и их приложения 2017 № 18 С. 136–138
В докладе рассматривается статистическая зависимость числа порожденных вершин дерева решений и физического времени работы программной реализации метода ветвей и границ для задачи коммивояжера (TSP). На основе результатов вычислительного эксперимента получено приближенное соотношение между числом  порожденных вершин (сложность индивидуальной TSP) и физическим временем. Предлагается использовать это эмпирическое соотношение для прогнозирования времени работы программы, решающей TSP с числом «городов» больше 40. ...
Added: March 22, 2020
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit