• 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 30, 2026
HSE Economists Reveal How the Wage Gap Emerges Among Vocational School Graduates
HSE researchers examined the careers of 600,000 graduates of Russian secondary vocational education programmes and found that at the start of their careers, the gender wage gap reaches 23%, doubling after three years. This disparity is largely due to male and female students choosing different occupations when enrolling in vocational schools. These were the findings made by Sergey Roshchin, Natalya Yemelina, and Ksenia Rozhkova from of the HSE Faculty of Economic Sciences. The article has been published in Educational Studies.
June 25, 2026
HSE Researchers Make Aldehydes Perform Dual Function
Chemists from HSE University have discovered a way to carry out a reductive addition reaction without using an external reducing agent. Instead, the required 'resource' is supplied by the aldehyde itself, one of the reaction participants. This approach helps prevent unwanted side reactions, reduces toxicity, and simplifies the production and synthesis of organic molecules, including those used in the manufacture of medicines. The study has been published in Journal of Catalysis.
June 25, 2026
HSE Scientists Explain Why Findings in Autism Research Differ
Researchers from the Cognitive Health and Intelligence Centre at HSE University conducted the first-ever systematic review of studies on the specifics of emotion-from-motion perception in autism. The review showed that differences found between autistic and non-autistic individuals are largely associated with the experimental design and the types of tasks given to study participants. The review findings have been published in Research in Autism.

 

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
Graph Games and Logic Design
Springer, 2026.
This book presents established and new research on the close connections between graph games and systems of logic, particularly existing and newly designed modal logics. The volume utilizes two graph games – the sabotage game and the hide-and-seek game – to demonstrate the natural interplay between designing new graph games and exploring new kinds of ...
Added: June 30, 2026
On Ω-stable 3-diffeomorphism with a solid or thickened surfaced basic set
Pochinka O., Barinova M., Journal of Geometry and Physics 2026 Vol. 228 P. 1–8
In the present paper we consider an Ω-stable 3-diffeomorphism with a solid or thickened surfaced non-trivial basic set. Such basic sets include, for instance, all one-dimensional expanding attractors and those two-dimensional basic sets that are not expanding. We prove that the chain recurrent set of every such a diffeomorphism necessarily contains at least two non-trivial ...
Added: June 30, 2026
Почти пустые симплексы и полиэдры Клейна
German O., Illarionov A., Известия РАН. Серия математическая 2026 Т. 90 № 3 С. 3–18
Пусть симплекс с целочисленными вершинами - содержащий ровно одну целочисленную точку, отличную от своих вершин. В работе доказывается, что если точка находится во внутренности симплекса или в относительной внутренности некоторой гиперграни симплекса, то объем симплекса ограничен величиной, зависящей только от размерности, в противном случае объем симплекса может быть сколь угодно большим. Этот результат применяется для вывода асимптотической формулы для среднего числа вершин полиэдров ...
Added: June 29, 2026
The 12th International Conference on Information Technology and Quantitative Management (ITQM 2025)
Netherlands: ScienceDirect, 2025.
No ...
Added: June 28, 2026
Object-centric process management: A research manifesto
Seidel A., Weske M., Montali M. et al., Information Systems 2026 Vol. 141 Article 102728
Business process management employs process models and event logs to represent the behavior of the information systems under study. Traditional case-centric notions consider the order of activities and events in isolated process instances. The emerging field of object-centric processes challenges this assumption by putting objects in the center. Object-centric process mining and modeling approaches identify ...
Added: June 27, 2026
2024 26th International Conference on Digital Signal Processing and its Applications (DSPA)
IEEE, 2024.
A.S. Popov Russian Science and Technical Society with support from V. A. Trapeznikov Institute of Control Sciences, V.A. Kotelnikov Institute of Radio Engineering and Electronics, Autex Ltd. is leading the ХХVIII International Conference «Digital Signal Processing and its Applications — DSPA-2024» ...
Added: June 27, 2026
Построение методик оценки качества восприятия (QOE) потокового видео
Ivchenko A., Дворкович А. В., Телекоммуникации 2020 Т. 12 С. 2–11
Dynamic Adaptive Streaming over HTTP (DASH) technology powers most multimedia services. Its specific features (re-buffering, quality switching, etc.) necessitate the development of specialized methods for assessing user subjective quality of experience (QoE) based on objective parameters. This article examines the impact of various metrics on QoE and presents assessment models with Spearman correlation coefficients up ...
Added: June 27, 2026
Generalized Hurst Hypothesis: Description of Time-Series in Communication Systems
Ivchenko A., Nigmatullin R. R., Dorokhin S. V., Mathematics 2021 Vol. 9 No. 4 Article 381
n this paper, we focus on the generalization of the Hurst empirical law and suggest a set of reduced parameters for quantitative description of long-time series. These series are usually considered as a specific response of a complex system (economic, geophysical, electromagnetic and other systems), where successive fixations of external factors become impossible. We consider ...
Added: June 27, 2026
Growth in noncommutative algebras and entropy in derived categories
Piontkovski D., / Series arXiv "math". 2026.
A noncommutative projective variety is defined, following Artin and Zhang, by a graded coherent algebra 𝐴. The category of coherent sheaves is then the quotient qgr(𝐴) of the category of finitely presented graded modules by the subcategory of torsion modules. We consider the categorical and polynomial entropies of the Serre twist, that is, of the ...
Added: June 23, 2026
Multilinear nilalgebras and the Jacobian theorem
Piontkovski D., / Series arXiv "math". 2025.
If a symmetric multilinear algebra is weakly nil, then it is Engel. This result may be regarded as an infinite-dimensional analogue of the well-known Jacobian theorem, which states that if a polynomial mapping has a polynomial inverse, then its Jacobian matrix is invertible. This refines a theorem of Gerstenhaber and partially answers a question posed ...
Added: June 23, 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
Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжёра
Ulyanov M., Fomichev M., Информационные технологии 2019 Т. 25 № 10 С. 590–595
The algorithm that implements the Branch and Bound method for solving the Traveling Salesman Problem is one of the common exact algorithms for solving it. Metaheuristic algorithms for solving this problem do not guarantee obtaining an exact solution, however they work "quickly". In order to reduce the nodes number of the generated decision tree in ...
Added: February 16, 2020
A Hybrid Exact Algorithm for the Asymmetric Traveling Salesman Problem: Construction and a Statistical Study of Computational Efficiency
Zhukova G., Ulyanov M., Fomichev M., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054–2067
We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin–Kernighan–Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show ...
Added: November 24, 2019
  • 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