• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • Эффективное вычисление всех допусков в разреженной задаче о максиминном пути
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Приоритетные направления
  • бизнес-информатика
  • государственное и муниципальное управление
  • гуманитарные науки
  • инженерные науки
  • компьютерно-математическое
  • математика
  • менеджмент
  • право
  • социология
  • экономика
по году
  • 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
  • еще
Тематика
Новости
13 ноября 2026 г.
НИУ ВШЭ и ИФТТ РАН заключили соглашение о создании совместной лаборатории
Церемония подписания соглашения о создании Лаборатории экспериментальных исследований и применений новых функциональных материалов состоялась 11 ноября в здании НИУ ВШЭ на Старой Басманной улице, где расположен факультет физики. Подписи под документом поставили ректор НИУ ВШЭ Никита Анисимов и врио директора Института физики твердого тела им. Ю.А. Осипьяна (ИФТТ) РАН Ирина Ибрагимова.
12 ноября 2026 г.
«Формулирование теорий - последний навык, в котором мы превосходим машины»
Луи Вервурт, доцент МИЭМ ВШЭ, специалист в области философии науки и искусственного интеллекта, рассказал «Вышке.Главное» о том, что общего у физики и философии, почему квантовая механика не согласуется с теорией относительности, как быть исследователем в эпоху ИИ и почему способность создавать новые теории может стать главным преимуществом человека перед машиной.
10 ноября 2026 г.
Ученые ФКН ВШЭ представили исследования в области тензорных методов на международной конференции в Китае
Исследователи Института искусственного интеллекта и цифровых наук факультета компьютерных наук НИУ ВШЭ приняли участие в Международной конференции-школе по тензорным методам в математике и вычислениях для искусственного интеллекта (3rd Conference-School on Tensor Methods in Mathematics and Artificial Intelligence Computing). Мероприятие прошло в конце октября в Шэньчжэне (Китай). Одна из работ ученых института получила награду Best Poster Award и вошла в число пяти лучших постеров конференции.

 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации
  • Книги
  • Статьи
  • Главы в книгах
  • Препринты
  • Верификация публикаций
  • Расширенный поиск
  • Правила использования материалов
  • Наука в ВШЭ

?

Эффективное вычисление всех допусков в разреженной задаче о максиминном пути

Успехи математических наук. 2024. Т. 79. № 5. С. 185–186.
Каймаков К. В., Малышев Д. С.

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

Научное направление: Математика Компьютерные науки
Язык: русский
Полный текст
DOI
Ключевые слова: комбинаторная оптимизацияустойчивость оптимального решениязадача о максиминном пути
Похожие публикации
The medial septum model as a pacemaker of theta rhythm: the key role of short-term synaptic plasticity
Mysin I. E., Dubrovin S. V., Cognitive Neurodynamics 2026 Vol. 20 No. 191 P. 1–30
Добавлено: 14 ноября 2026 г.
Траектории ставок как сигнал сговора: LSTM-классификация аукционов государственных закупок
Ефимов К. Д., Журнал Новой экономической ассоциации 2026 № 72 С. 105–114
В работе предлагается метод автоматического выявления картель ного поведения в электронных аукционах государственных закупок на основе анализа пол ной траектории ставок. Эмпирическая база включает 508 историй торгов за 2016–2020 гг. с электронной площадки РТС-тендер; положительный класс размечен по материалам дел ФАС России, контрольная группа сформирована из сопоставимых аукционов без зафикси рованных нарушений. Каждая сессия представлена ...
Добавлено: 13 ноября 2026 г.
Model-Dependent Prompt-Component Ablation for Medical LLM Decision Support: Application to ENT Biologics Screening
Sergey N. Koltcov, Budkovaia M., Сурков А. Ю. и др., IEEE Journal of Biomedical and Health Informatics 2026 P. 1–10
Добавлено: 13 ноября 2026 г.
Upper Bound for Permanent Saturation of Metric Graphs using Interval Exchange Transformations
Ермолаев Е. С., Чернышев В. Л., Скрипченко А. С., Journal of Nonlinear Science 2026 Vol. 36 No. 122 (2026) P. 1–37
We study upper bounds for the moment of permanent -saturation in finite metric graphs. The dynamics is generated by moving points travelling with unit speed along edges and branching into all outgoing directions whenever they reach a vertex. We first reformulate this branched dynamics in terms of birth times at vertices and prove a sufficient ...
Добавлено: 12 ноября 2026 г.
Impact of 5G NR-V2X Message Losses on Connected Vehicle Warning Functions
Физулин А. В., Степанянц В. Г., Американов А. А. и др., FUTURE TRANSPORTATION 2026 Vol. 6 No. 6 Article 264
Добавлено: 12 ноября 2026 г.
On β-function of 𝒩 = 2 supersymmetric integrable sigma models. Part II
Alfimov Mikhail, Kurakin Andrey, Journal of High Energy Physics 2026 Vol. 2026 Article 99
Добавлено: 12 ноября 2026 г.
Kripke Completeness For Predicate Modal Logics Of Bounded Alternativity: First Steps
Шехтман В. Б., Shkatov D., Review of Symbolic Logic 2026 Vol. 19 No. 4 P. 859–882
Добавлено: 12 ноября 2026 г.
On flexibility of trinomial varieties
Игнатьев М. В., Вилкин Т. В., Mediterranean Journal of Mathematics 2026 Vol. 23 No. 2 Article 70
Добавлено: 12 ноября 2026 г.
Линейные отображения, сохраняющие матрицы с n или n − 1 различными собственными значениями
Максаев А. М., Промыслов В. В., Тишутин П. С., Записки научных семинаров ПОМИ РАН 2026 Т. 554 С. 218–235
Пусть K — алгебраически замкнутое поле, а ℰₖ — множество n × n матриц над K, имеющих ровно k различных собственных значений. Ранее классификация линейных отображений T: Mₙ(K) → Mₙ(K), удовлетворяющих условию T(ℰₙ) ⊆ ℰₙ, была получена для обратимых отображений над полем характеристики 0. В данной работе эта классификация распространяется на произвольные, в том числе ...
Добавлено: 11 ноября 2026 г.
Nonexistence of Energy Function for Surface Diffeomorphisms with Nontrivial Basic Sets of Serpentine Geometric Type
Баринова М. К., Tirskaya Karina, Владикавказский математический журнал 2026 Vol. 28 No. 3 P. 25–43
В работе исследуется проблема существования энергетической функции для дискретных динамических систем, заданных структурно устойчивыми диффеоморфизмами на гладких, компактных, ориентируемых поверхностях без края. Для рассматриваемого класса такая функция определяется как непрерывная функция, убывающая вдоль орбит системы вне неблуждающего множества и постоянная на неблуждающих орбитах. На данный момент известно, что если неблуждающее множество структурно устойчивого диффеоморфизма поверхности ...
Добавлено: 11 ноября 2026 г.
О статистических свойствах наилучших диофантовых приближений
Илларионов А. А., Математический сборник 2026 Т. 217 № 11 С. 56–87
Пусть $b(\alpha;T)$ --- количество наилучших совместных диофантовых приближений с общим знаменателем $\le T$ к точке $\alpha \in {\Bbb R}^n$. Мы выводим асимптотические формулы для среднего значения этой величины (усреднение проводится по всем рациональным точкам вида $\alpha = (k_1/N,\ldots, k_n/N)$, $N\le R$), а также для ее математического ожидания при условии, что $\alpha$ равномерно распределена на кубе $[0,1)^n$. ...
Добавлено: 10 ноября 2026 г.
Structural model of decision support system for sustainable development of oil and gas companies
Stoianova A. D., Trofimets V. Y., Matrokhina K. V., International Journal of Engineering, Transactions A: Basics 2025 Vol. 38 No. 4 P. 701–709
Добавлено: 10 ноября 2026 г.
К теореме Гудмана-Штрауса
Верещагин Н. К., Математический сборник 2026 Т. 217 № 10 С. 3–46
Теорема Гудмана-Штрауса утверждает, что для “почти всякой” подстановки семейство подстановочных замощений софично, т.е. может быть задано локальными правилами для некоторой раскраски плиток. Условия на подстановку, гарантирующие софичность, довольно сложные. В настоящей работе мы предлагаем версию теоремы Гудмана-Штрауса с более простыми условиями на подстановку. Хотя эти условия достаточно ограничительны, мы показываем, что в сочетании с двумя простыми приемами (взятием достаточно ...
Добавлено: 10 ноября 2026 г.
EdFitter: a hybrid course recommendation system using large language models
Sergei Koltcov, Рюмин Д. А., Alexandr Axyonov и др., PeerJ Computer Science 2026 Article 12:e4141
Добавлено: 10 ноября 2026 г.
Assessing density equilibration in confined Liquid–Liquid interfaces
Guskov T., Gerke K., Кондратюк Н. Д. и др., Molecular Simulation 2026 Vol. 52 No. 7 P. 546 – 555
Добавлено: 10 ноября 2026 г.
Influence of nuclear quantum effects on metastable states of warm dense hydrogen
Lukyanchuk V., Норман Г. Э., Кондратюк Н. Д. и др., Scientific Reports 2026 Vol. 16 No. 1 Article 16435
Добавлено: 10 ноября 2026 г.
Machine Learning and Knowledge Discovery in Databases. Research Track and Applied Data Science Track. European Conference, ECML PKDD 2026, Naples, Italy, September 7–11, 2026, Proceedings
Cham: Springer, 2027.
Добавлено: 9 ноября 2026 г.
Artificial Intelligence for Software Engineering (AI4SE): A Review of Capabilities, Evaluation, and Verification Challenges
Avdoshin S.M., Pesotskaya E.Y., Proceedings of the Institute for System Programming of the RAS 2026 Vol. 38 No. 6, part 2 P. 133–146
Добавлено: 8 ноября 2026 г.
АЛГОРИТМ ГЕНЕТИЧЕСКОЙ ИНЖЕНЕРИИ (GEA): ЭФФЕКТИВНЫЙ МЕТАЭВРИСТИЧЕСКИЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ
Сохраби М., Фатхоллахи-Фард А. М., Громов В. А., Автоматика и телемеханика 2024 № 3 С. 23–37
Генетические алгоритмы (ГА) известны своей эффективностью в решении задач комбинаторной оптимизации благодаря их способности исследовать разнообразные пространства решений, обрабатывать различные представления, использовать параллелизм, сохранять хорошие решения, адаптироваться к изменяющимся условиям, управлять комбинаторным разнообразием и проводить эвристический поиск. Тем не менее такие ограничения, как преждевременная сходимость, неспецифичность и стохастичность операторов кроссовера и мутации, делают ГА не ...
Добавлено: 8 мая 2024 г.
Exact Algorithm for Generating H-Cores in Simplified Lattice-Based Protein Model
Игнатов А. Д., , in: 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers. Communications in Computer and Information Science (CCIS, volume 1913)Vol. 1913.: Springer, 2023. P. 173–187.
Добавлено: 18 января 2024 г.
Competitive Intensity and Quality Maximizing Seedings in Knock-out Tournaments
Дагаев Д. А., Суздальцев А. И., Journal of Combinatorial Optimization 2018 Vol. 35 No. 1 P. 170–188
Добавлено: 1 августа 2017 г.
An enhanced bitstring encoding for exact maximum clique search in sparse graphs
Pablo San Segundo ., Jorge Artieda .., Mikhail Batsyn и др., Optimization Methods and Software 2017 Vol. 32 No. 2 P. 312–335
Добавлено: 9 марта 2017 г.
Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений
Грибанов Д. В., Малышев Д. С., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19–31
Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...
Добавлено: 20 октября 2016 г.
Методы комбинаторной оптимизации. Метод ветвей и границ в решении задач химической технологии и логистики
Мешалкин В. П., Заходякин Г. В., Ходченко С. М., М.: РХТУ им. Д.И. Менделеева, 2013.
Изложены разделы теории графов и комбинаторного анализа, сущность и применение методов комбинаторной оптимизации на основе одного из широко распространенных методов комбинаторного поиска оптимальных решений – метода ветвей и границ для решения прикладных задач в химической технологии, ресурсоэнергоэффективной инженерно-технической организации сложных химико-технологических систем и логистике ресурсоэнергосбережения. Указанные задачи относятся к классу комбинаторных задач неполиномиальной сложности (NP-задач ...
Добавлено: 27 февраля 2016 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика обработки персональных данных
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору