The Mixed Chinese Postman Problem

M.K. Gordenko; S.M. Avdoshin

doi:10.15514/ISPRAS-2017-29(4)-7

Публикации

?

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

Задачи маршрутизации важны для областей логистики и управления трансортом. Задачи маршрутизации в основном связаны с определением оптимального набора путей в мультиграфе. Задача китайского почтальона (CPP) является особым случаем задачи маршрутизации, имющим много потенциальных приложений. Мы предлагаем решение MCPP (специального NP-полного случая CPP на смешанном мультиграфе) с использованием редуцирования исходной задачи к обобщенной задаче коммивояжера (General Traveling Salesman Problem, GTSP). Указываются варианты CPP. Представлены математические формулировки некоторых проблем. Показан алгоритм редуцирования MCPP в мультиграфе к GTSP. Приводятся экспериментальные результаты решения MCPP в мультиграфе посредством редуцирования к GTSP.

Научное направление: Математика Компьютерные науки

Приоритетные направления: компьютерно-математическое

Язык: английский

Полный текст

DOI

Текст на другом сайте

Ключевые слова: задача коммивояжера Traveling Salesman Problem heuristic algorithm эвристический алгоритм Mixed Chinese Postman Problem Arc Routing Problem Смешанная задача китайского почтальона Задача маршрутизации дуг

On the rate of Gaussian approximation for online linear regression problems

Шешукова М. Е., Durmus A., Khusainov M. и др., Statistics 2026 P. 1–25

Добавлено: 4 сентября 2026 г.

Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence (UAI), PMLR Volume 337, 17-21 August 2026, KIT, Amsterdam, the Netherlands

Proceedings of Machine Learning Research , 2026.

Добавлено: 4 сентября 2026 г.

Относительные аналитические законы взаимности

Осипов Д.В., Математический сборник 2026 Т. 217 № 9 С. 130–146

Изучаются законы взаимности, связанные с комплексными линейными расслоениями на расслоениях на ориентируемые окружности. В частности, доказывается следующий закон взаимности. Пусть B – комплексное многообразие и πi:Mi→B – расслоение на ориентируемые окружности, где индекс i пробегает конечное множество. Пусть Li и Ni – комплексные линейные расслоения на каждом многообразии Mi. Закон взаимности утверждает, что сумма всех элементов (πi)∗(c1(Li)∪c1(Ni)), где (πi)∗ – ...

Добавлено: 3 сентября 2026 г.

A unified frequency-domain framework for tilted slice localization and ischemic stroke detection

Khodadoust J., Куликова С. П., Khodadoust F., Biomedical Signal Processing and Control 2027 Vol. 129 P. 111284–111284

Анализ острого ишемического инсульта (ОИИ) по двухмерным (2D) клиническим изображениям затруднен из-за неконтролируемого наклона срезов и геометрических несоответствий, нарушающих предположения моделей глубокого обучения (ГБО), не зависящих от положения. В данной статье предлагается унифицированная, учитывающая геометрию, частотно-доменная структура для локализации наклонных срезов и сегментации ишемического инсульта, которая явно разделяет оценку положения и анализ поражения. Метод сначала ...

Добавлено: 2 сентября 2026 г.

Proceedings of the 2026 Fourth International Conference on Distributed Computing and High Performance Computing (DCHPC)

IEEE, 2026.

Добавлено: 2 сентября 2026 г.

Orbifold Saito theory of A and D type singularities

Басалаев А. А., Раровский А. А., Journal of Singularities 2026 Vol. 30 P. 61–80

Добавлено: 1 сентября 2026 г.

Non-axiomatizability of modal predicate logics of Dedekind-complete linear orders with constant domains

Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2026 Vol. 36 No. 6 Article exag026

Добавлено: 1 сентября 2026 г.

Semi-Interlaced Polytopes

Селянин Ф. И., Moscow Mathematical Journal 2026 Vol. 26 No. 2 P. 167–187

Добавлено: 31 августа 2026 г.

A new spin on polynomial relations among kappa classes

Казарян М. Э., Дунин-Барковский П. И., Бычков Б. С. и др., International Mathematics Research Notices 2026 Vol. 14 Article rnag146

Добавлено: 31 августа 2026 г.

Any Topological Recursion on a Rational Spectral Curveis KP Integrable

Казарян М. Э., Дунин-Барковский П. И., Бычков Б. С. и др., Communications in Mathematical Physics 2026 Vol. 407 No. 69

Добавлено: 31 августа 2026 г.

Сплетенный мир: кошка перевернулась. Доклад Римскому клубу

Громов В. А., Переслегин С. Б., Переслегина Е. Б. и др., СПб.: Полакс, 2026.

Механизм происходящих в мире изменений носит эволюционный, а не экологический характер. Иначе говоря, Человечество столкнулось с кризисом развития, который имеет три независимые составляющие: кризис индустриального общества (фазовый кризис), кризис научного мышления (эпистемный кризис) и кризис формата существования разума (социосистемный кризис). Доклад посвящён аспектам этого триединого кризиса и возможным путям его преодоления, не сводящимся к первичному ...

Добавлено: 31 августа 2026 г.

Multiplicity-free products of Schubert divisors

Devyatov R. A., Mathematical notes 2026 Vol. 119 No. 3 P. 782–786

Добавлено: 30 августа 2026 г.

Mukai models of Fano varieties

Bayer A., Кузнецов А. Г., Macrì E., Journal fuer die reine und angewandte Mathematik 2026 Vol. 2026 No. 836 P. 111–162

Добавлено: 30 августа 2026 г.

Mukai bundles on Fano threefolds

Bayer A., Кузнецов А. Г., Macrì E., Compositio Mathematica 2026 Vol. 162 No. 1 P. 59–99

Добавлено: 30 августа 2026 г.

Full exceptional collections on the symplectic isotropic Grassmannians

Гусева Л. А., Novikov A., Advances in Mathematics 2026 Vol. 503 Article 111211

Добавлено: 30 августа 2026 г.

On calibration of remote sensing retrievals of ecosystem respiration (Reco) with tower measurements over,Russian forests and wetlands

Shabanov N., Kuricheva O., Kurbatova J. и др., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.

Добавлено: 21 августа 2026 г.

Three Algorithms for Merging Hierarchical Navigable Small World Graphs

Пономаренко А. А., / Series Computer Science "arxiv.org". 2025.

Добавлено: 30 июля 2026 г.

Growth in noncommutative algebras and entropy in derived categories

Пионтковский Д. И., / Series arXiv "math". 2026.

Добавлено: 23 июня 2026 г.

Multilinear nilalgebras and the Jacobian theorem

Пионтковский Д. И., / Series arXiv "math". 2025.

Добавлено: 23 июня 2026 г.

ML-based Fast Simulation of FARICH Responses

Шипилов Ф. А., Barnyakov A., Ivanov A. и др., / Series Physics "arxiv.org". 2026.

Добавлено: 19 мая 2026 г.

Natural hazard database from Internet publications: text mining with a large language model

Деркачева А. А., Сакиркина М. А., Краев Г. Н. и др., /. 2026.

Добавлено: 28 апреля 2026 г.

Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena

Пиле Я. Э., Deng Y., Щур Л. Н., / Series arXiv "math". 2026. No. 2604.10254.

Добавлено: 20 апреля 2026 г.

Using predefined vector systems to speed up neural network multimillion class classification

Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.

Добавлено: 2 апреля 2026 г.

Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection

Сорокин К. С., Бекетов М. Е., Онучин А. и др., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.

Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, ...

Добавлено: 15 января 2026 г.