Эффективные алгоритмы для решения задач о заданном порядковом расстоянии, о геометрическом минимальном остовном дереве и о максиминных путях тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Каймаков Кирилл Владимирович

• Каймаков Кирилл Владимирович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Каймаков Кирилл Владимирович

2.2.4 Описание алгоритма

2.2.5 Доказательство корректности и вывод оценки трудоемкости

2.2.6 Вычислительные эксперименты

3 Эффективные алгоритмы для двух задач комбинаторной оптимизации

3.1 Алгоритм для эффективного решения ОЗМП

3.1.1 Описание алгоритма, корректность и трудоемкость его работы

3.1.2 Вычислительные эксперименты

3.2 Алгоритм для эффективного решения к-ЗМП

3.2.1 Описание алгоритма, корректность и трудоемкость его работы

3.2.2 Вычислительные эксперименты

3.3 Алгоритм для онлайнового эффективного анализа чувствительности оптимальных решений ЗМП

3.3.1 Эффективное вычисление допусков для ЗМОД

3.3.2 Описание алгоритма

3.3.3 Вычислительные эксперименты

Заключение

Литература

Приложения

Приложение

Приложение

Приложение

Приложение

Введение

1. Актуальность и степень разработанности темы исследований, формулировки основных результатов диссертации

Структуры данных играют ключевую роль в оптимизации алгоритмов, позволяя эффективно хранить и получать доступ к информации. Правильный выбор структуры данных может значительно сократить время выполнения алгоритма, особенно при обработке больших объемов данных. Например, использование хэш-таблицы позволяет быстро находить нужный элемент в массиве, а применение бинарного дерева поиска обеспечивает эффективную сортировку и поиск данных. Комбинирование различных алгоритмических приемов, как пазлов, позволяет создавать мощные и эффективные решения для сложных задач. Например, объединение алгоритмов машинного обучения с алгоритмами оптимизации может привести к разработке более точных моделей прогнозирования. В данной диссертации на основе эффективного использования структур данных и комбинирования алгоритмических приемов предлагаются несколько алгоритмов для решения некоторых задач комбинаторной оптимизации и вычислительной геометрии, улучшающих ранее известные решения.

Классическая в вычислительной геометрии задача о паре ближайших точек состоит для заданного множества п точек в ¿-мерном пространстве в том, чтобы найти пару ближайших точек по какой-нибудь норме. Для оффлайновой или онлайновой (когда точки заранее неизвестны и поступают одна за другой) постановок этой задачи тривиальный алгоритм перебора всех пар точек имеет сложность 0(п2) при фиксированном Оказывается, что для

любых фиксированных d и s ^ 1 по норме ls офлайновая задача может быть решена за время O(nlogn) [27]. В модели вычислений, когда атомарной операцией считается вычисление целой части числа, она может быть решена за время O(n log log n) [39]. В этой же модели вычислений оффлайновая задача о паре ближайших точек решается рандомизированным алгоритмом (см, например, [55]) сложности O(n). Для ее онлайновой постановки имеется алгоритм сложности O(logn) на обработку каждой точки [18].

Естественным образом определяемая задача о k парах ближайших точек является обобщением задачи о паре ближайших точек. Ее оффлайновая версия может быть решена, см. работу [59, 60], за время O(n log n + k) при любом фиксированном d. Некоторые приложения задачи о k парах ближайших точек (такие, как проектирование СБИС или геоинформационные системы) и алгоритмы для ее решения представлены в [11, 28, 58]. Для любых е > 0 и 1 ^ k ^ (2) во второй главе диссертации разработан алгоритм сложности O(n log n log 1) для е-приближенного вычисления k-ого порядкового расстояния по li/l^-норме в системе n заданных точек единичного квадрата. При фиксированном е и n log n = o(k) наш алгоритм работает быстрее, чем известные алгоритмы для оффлайновой задачи о k парах ближайших точек.

Задача о минимальном остовном дереве (кратко, ЗМОД) — это классическая задача комбинаторной оптимизации. Эта задача для заданного связного взвешенного по ребрам графа состоит в том, чтобы найти в нем остовное дерево, т.е. связный ациклический подграф, содержащий все вершины графа, с минимальной суммой весов его ребер. ЗМОД имеет многочисленные приложения не только в алгоритмической теории графов (см., например, обзор [47]), но еще и в анализе данных [10], компьютерном зрении [37], проектировании интегральных схем [66], анализе финансовых рынков [63] и многих других.

К настоящему времени для решения ЗМОД на графах c n вершинами и m ребрами разработано несколько эффективных алгоритмов: алгоритм Борувки со сложностью O(mlogn) (см. [20, 74]), алгоритм Крускала

со сложностью O(m logn) (см. [56, 74]), алгоритм Прима со сложностью O(m + nlogn) (см. [40, 68]), алгоритм Шазелла со сложностью O(ma(m,n)) [23], где а(-, •) — обратная функция Аккермана, и ряд других. Все эти алгоритмы являются детерминированными.

На настоящее время открытой проблемой является разработка детерминированного алгоритма решения ЗМОД со сложностью O(m) (или доказательство его отсутствия), и на настоящее время алгоритм Шазелла является рекордным по вычислительной сложности среди детерминированных алгоритмов. Ожидаемой линейной сложности удается добиться за счет рандомизации, соответствующий алгоритм был разработан Каржером, Клейном и Тарджаном в [53]. Для некоторых отдельных классов графов или семейств классов графов удается построить детерминированные алгоритмы решения ЗМОД линейной сложности. Например, для классов графов, отличных от множества всех графов и замкнутых относительно удаления вершин и ребер, а также стягивания ребер, ЗМОД может быть решена за линейное время [64].

Вызывает особый интерес класс геометрических ЗМОД, т.е. задач вычисления МОД в полных графах на системах n точек d-мерного пространства

l~d

с 1р-нормой ||x,y||p = {/Х^ |x — Vilp, где p ^ 1, между точками. Во-первых,

у i=1

геометрические ЗМОД возникают в алгоритмах кластеризации (см., например, [10]) и эффективные алгоритмы решения этих ЗМОД ускоряют сами алгоритмы кластеризации. Во-вторых, некоторые из них могут быть решены за время, меньшее, чем O(m) = O(n2). Например, при d = 2 и p =1 за время

O(n logn) [48, 81], при d = 2 и p = 2 за время O(n logn) [70], для p = 2 за вре-

2__2 + ^

мя O((nlogn)з) (d = 3) и для любого е > 0 за время O(n г) (d ^ 4) [6]. Для d = p = 2 соответствующая геометрическая ЗМОД может быть решена (см. работу [31]) рандомизированным алгоритмом с ожидаемым временем работы O(n log* n), где log* n — итерированный логарифм.

Для случая p = 1 наиболее важные результаты представлены в работах [41] и [57]. В первой из них доказано, что при любом фиксированном d ^

соответствующая геометрическая ЗМОД может быть решена за время

(log n + logrd n log log n)),

где rd G {0,1, 2, 4} при d G {2,3, 4, 5} и rd = d при d ^ 6. Во второй показано, что для d = 3 она может быть решена со сложностью O(n log n).

Во второй главе диссертации при d ^ 5 улучшается результат из работы [41]. А именно, там доказывается, что для любого фиксированного d ^ 2 ЗМОД на любой системе n точек пространства Rd c ^-нормой между точками может быть решена за время O(n logd-1 n)

Задача о максиминном пути (кратко, ЗМП) для заданных связного графа G = (V, E), пропускных способностей его ребер c : E —> r^0 и вершин s,t G V состоит в том, чтобы найти

b(s,t) = max min c(e) или arg max min c(e),

Pgpst egP °Pgpst egP

где Pst обозначает множество всех путей между s и t.

ЗМП возникает в качестве отдельной подзадачи в алгоритме Эдмондса и Карпа [35] для вычисления максимального потока в сети, а также в алгоритме решения задачи о k-расщепляемом потоке [13]. Задача о максимальном потоке в сети возникает, например, в математических моделях передачи электроэнергии, планирования полетов, сетях связи. Вариант ЗМП, когда фиксируется s, а t пробегает все множество вершин, возникает в качестве подзадачи в планировании расписания движения железнодорожного транспорта, см., например, [61].

ЗМП для графа с n вершинами и m ребрами может быть решена алгоритмом Камерини [22] за время O(m). Вариант ЗМП, когда задана только вершина s, а t пробегает все множество значений из V, может быть решена (см. работу [33]) за время

O(а/mn log(n) loglog(n) + m\Jlog(n)).

Имеются несколько работ (см., например, [24, 34, 52, 72, 79]), в которых предложены алгоритмы с оценками их вычислительной сложности для решения

вариантов ЗМП, когда рассматриваются ориентированные графы и/или s,t пробегают все вершины.

В третьей главе диссертации рассматриваются онлайновая ЗМП и задача о k максиминных путях. В первой задаче (кратко, ОЗМП) предполагается, что граф (G,c) известен заранее, а пары (s,t) поступают онлайн. Вторая (кратко, k-ЗМП) состоит для заданных (G, с) и пар (s1? t1),..., (sk, tk) в том, чтобы найти b(si,ti) для любого i G [k]. В третьей главе диссертации для решения ОЗМП предлагается алгоритм с временем предобработки O(m + n logn) графа (G,c) и временем O(logn) обработки каждого запроса (s,t). Этот алгоритм решения ОЗМП сразу дает алгоритм сложности O(m + (n + k) logn) для решения k-ЗМП. В третьей главе диссертации для решения задачи k-ЗМП предлагается альтернативный оффлайновый алгоритм с тем же ожидаемым временем работы.

Допуском элемента задачи комбинаторной оптимизации (кратко, ЗКО) по отношению к заданному оптимальному решению называется максимальное изменение, т. е. уменьшение или увеличение его стоимости, при котором это решение остается оптимальным. Допуски дают информацию об устойчивости оптимального решения относительно возмущений его элементов. Они также использовались для построения алгоритмов для решения NP-трудных и полиномиально решаемых ЗКО, таких как варианты задачи о назначениях [30], задача коммивояжера [43, 78], задача выбора маршрута транспортного средства [14], задача о взвешенном независимом множестве [46], см. также обзоры [76, 77, 78]. Вопрос об эффективности вычисления допусков элементов ЗКО представляет самостоятельный интерес, ему было посвящено несколько работ, см., например, работы [19, 26, 32, 45, 51, 62, 67, 69, 71, 73].

ЗКО на максимум определяется четверкой параметров (E, F, с, fc), где E — конечное базовое множество элементов, F С 2E \ {0} — множество допустимых решений, с : E —> R — функция стоимости, fc : F —> R — целевая функция. Допустимое решение S* G F называется оптимальным

решением ЗКО, если fc(S*) = maxfc(S). Функция /c(-) называется аддитив-

S gF

ной, если fc(S) = ^ c(e), и максиминной, если fc(S) = min c(e). Имеется

eGS eGS

множество конкретных аддитивных и максиминных ЗКО, см., например, работы [8, 9, 21, 25, 54].

Пусть П = (E, F, c, fc) — экземпляр ЗКО на максимум, e G E и a G r — некоторая константа. Через Пе а = (E, F, ce,a,fce а) обозначается экземпляр ЗКО на максимум, где

Ce,a(e) = c(e) + a,ce,a(e') = c(e') Ve' = e.

Пусть S* — оптимальное решение задачи П и e G E. Верхний допуск элемента e (относительно S*) определяется следующим образом:

us*(e) = sup{a G r^0 : S* является оптимальным решением Пе,а}.

Нижний допуск элемента e (относительно S*) определяется следующим образом:

Is*(e) = sup{a G r^0 : S* является оптимальным решением Пе,—a}.

Через F+e и F-e обозначаются множества тех допустимых решений задачи П, которые содержат или не содержат e, соответственно, т.е.:

F+e = {S G F : e G S}, F-e = {S G F : e G S}.

Через fc(F),fc(F+e) и fc(F—e) обозначены оптимальные значения целевой функции на F, F+e, F-e, т.е.:

fc(F) = m^ fc(S), fc(F+e) = max fc(S), fc(F-e) = max fc(S). SGF SGF+e SGF-e

Следующее утверждение было опубликовано в работе [44], см. Теоремы 4 и 15 из той работы:

Утверждение. Пусть П = (E, F, c, fc) — экземпляр ЗКО на максимум, S* — произвольное оптимальное решение П, e G E — произвольный элемент базового множества. Если П — аддитивная задача, то

uS*(e) = fc(F) — fc(F+e), если e G E \ S*, uS*(e) = если e G S*;

lS* (e) = fc(F) - fc(F_e), если e e S *, lS* (e) = если e gE \ S *.

Если П — максиминная задача, то

uS * (e) = fc(F) _ c(e), если e eE \ S * и max min c(e') > c(e),

SeF+e e'eS\{e}

uS*(e) = иначе; lS* (e) = c(e) _ fc(F_e), если e e S*, lS* (e) = если e eE \ S*.

В третьей главе диссертации предлагается алгоритм сложности O(ma(m,n)) для предобработки заранее заданных графа (G,c), где c(ei) = c(e2) Vei = e2, и его вершин s и t, при помощи которой за константное время можно вычислять верхние и нижние допуски любого ребра относительно некоторого максиминного st-пути. Это дает алгоритм совместного поиска оптимального решения ЗМП и вычисления допусков всех ребер сложности O(ma(m,n)), что для разреженного случая лучше сложности O(m + n log n) известного алгоритма Рамасвами-Орлина-Чакраварти [69].

2. Цели и задачи работы

Целями данного диссертационного исследования являются развитие известных структур данных и алгоритмических приемов, а также построение с их использованием эффективных алгоритмов для решения нескольких задач комбинаторной оптимизации и вычислительной геометрии.

Задачи диссертационного исследования:

1. Разработать эффективные алгоритмы для задач о k-ом порядковом расстоянии на точках единичного квадрата c li/l^-нормой и о минимальном остовном дереве на пространственных точках с ^-нормой.

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

Введение диссертации (часть автореферата) на тему «Эффективные алгоритмы для решения задач о заданном порядковом расстоянии, о геометрическом минимальном остовном дереве и о максиминных путях»

3. Научная новизна работы

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

4. Теоретическая и практическая значимость работы

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

5. Методология и методы диссертационного исследования

В диссертации использованы методы теории алгоритмов и анализа сложности вычислений, комбинаторной оптимизации и вычислительной геометрии.

6. Положения, выносимые на защиту, и личный вклад соискателя

На защиту выносятся следующие результаты диссертации:

1. Для любых е> 0 и 1 ^ k ^ Q) разработан алгоритм сложности O(n log n log I) для е-приближенного вычисления k-ого порядкового расстояния по 11/1то-норме в системе n заданных точек единичного квадрата.

2. Для любого фиксированного d ^ 2 разработан алгоритм сложности O(n logd-1 n) для вычисления минимального остовного дерева на n заданных точках d-мерного пространства в 11-норме.

3. Для решения онлайновой задачи о максиминном пути на заданном графе с n вершинами и m ребрами предложен алгоритм сложности O(log n) и с временем предобработки O(m + n log n). Для решения задачи о k макси-минных путях на заданном графе с n вершинами и m ребрами предложен алгоритм с ожидаемым временем работы O(m + (n + k) log n).

4. Для вычисления верхнего и нижнего допусков произвольного ребра в

инъективной задаче о максиминном пути между двумя заданными вершинами на заданном графе с n вершинами и m ребрами предложен алгоритм единичной сложности с временем предобработки O(ma(m,n)).

Все основные результаты диссертации получены лично соискателем. Научному руководителю принадлежат общее руководство диссертационным исследованием, предложения по редактуре текста и оптимизация некоторых незначительных частей алгоритмов.

7. Объем и структура работы

Диссертация состоит из введения, трех глав, заключения, списка литературы, включающего 81 наименований, и приложения, включающего свидетельства четырех программ для ЭВМ и их программный код. Общий объем диссертации составляет 108 страниц.

Во введении обосновывается актуальность диссертационной работы, представлены обзор литературы по теме исследований, цели и задачи работы, научная новизна диссертации, теоретическая и практическая значимость работы, методы диссертационного исследования, основные результаты диссертации, структура работы, а также представлены степень достоверности результатов работ, апробации результатов работ и публикации по теме диссертации.

В первой главе диссертации приводятся постановки рассматриваемых задач вычислительной геометрии и комбинаторной оптимизации, а также некоторое предварительное алгоритмическое обеспечение, которое будет использоваться в последующих главах настоящей диссертации.

Во второй главе диссертации для любых 1 ^ k ^ Q) и е> 0 излагается е-приближенный алгоритм сложности O(n log n log 1) для решения задачи о k-ом порядковом расстоянии в системе n точек единичного квадрата с 11 //^-нормой. Там же при любом фиксированном d описывается алгоритм сложности O(n logd-1 n) для вычисления минимального остовного дерева на n точках d-мерного пространства с /1-нормой.

В третьей главе диссертации рассматривается несколько задач комбинаторной оптимизации, связанных с максиминными путями в графах с n вершинами и m ребрами. Для решения онлайновой задачи о максиминном пути там излагается алгоритм сложности O(log n) с временем предобработки O(m + n log n), а для задачи о k максиминных путях там описывается алгоритм с ожидаемым временем работы O(m + (n + k) log n). В третьей главе предложена предобработка сложности O(ma(m,n)) заданных графа с попарно различными пропускными способностями ребер и двух его вершин, позволяющая за константное время вычислять нижний и верхний допуски произвольного ребра относительно максиминного пути между этими вершинами.

В заключении подводится итог к проделанной работе и обсуждаются перспективы дальнейшего развития тематики диссертационного исследования.

8. Степень достоверности и апробации результатов работы, публикации автора по теме диссертации

Все результаты, выносимые на защиту, являются новыми и достоверными. Это подтверждается как наличием строгих обоснований корректности и времени работы разработанных алгоритмов, опубликованных в ведущих рецензируемых научных изданиях, так и программной реализацией и тестовой верификацией этих алгоритмов. Результаты диссертации докладывались и обсуждались на следующих конференциях и семинарах:

1. XIV Международная конференция по сетевому анализу NET 2024 (Нижний Новгород, 2024).

2. Школа-конференция «Аппроксимации, графы, сети и интеллектуальный анализ данных» (Сочи, 2024).

3. XX Международная научная конференция «Проблемы теоретической кибернетики» (Москва, 2024).

4. Семинар международной лаборатории теоретической информатики НИУ ВШЭ.

5. Семинар лаборатории комбинаторных и геометрических структур МФТИ.

6. Общегородские семинары г. Н. Новгорода по дискретной математике.

7. Семинары лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ НН.

По теме диссертации имеются 5 работ в изданиях из перечней НИУ ВШЭ и ВАК РФ, в которых должны быть опубликованы основные научные результаты на соискание ученой степени кандидата наук:

1. Kaymakov K.V., Malyshev D.S. On efficient algorithms for bottleneck path problems with many sources // Optimization Letters. 2024. Vol. 18. P. 12731283, список А.

2. Каймаков К.В., Малышев Д.С. Приближенный поиск k-ого порядкового расстояния в системе точек единичного квадрата // Математические заметки. 2024. Т. 116, № 4. C. 502-507, список B.

3. Каймаков К.В., Малышев Д.С. Эффективное вычисление всех допусков в разреженной задаче о максиминном пути // Успехи математических наук. 2024. Т. 79, № 5. С. 203-204, список А.

4. Kaymakov K.V., Malyshev D.S. Efficient online sensitivity analysis for the injective bottleneck path problem // Optimization Letters. 2024, accepted, doi: 10.1007/s11590-024-02170-5, список А.

5. Каймаков К. В., Малышев Д. С. Эффективный поиск минимального дерева на точках пространства в li-норме // Математические Заметки. 2025. Т. 117, № 6, принята в печать, список B.

По теме диссертации также имеются несколько свидетельств о регистрации программ для ЭВМ:

1. Свидетельство о государственной регистрации программы для ЭВМ № 2024689963 от 11.12.2024: Программа для эффективного вычисления

заданного порядкового Манхэттенского расстояния между точками на плоскости с данной точностью, Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Высшая школа экономики».

Ссылка на репозиторий С1ШиЬ:

https://github.com/Kirundel/PHD/tree/main/KthMD

2. Свидетельство о государственной регистрации программы для ЭВМ № 2024691203 от 20.12.2024: Программа для эффективного поиска минимального дерева на точках трехмерного пространства в Манхэттенской норме, Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Высшая школа экономики».

Ссылка на репозиторий С^^Ь:

https://github.com/Kirundel/PHD/tree/main/MST3D_RID

3. Свидетельство о государственной регистрации программы для ЭВМ №2024667694 от 29.07.2024: Программа для эффективного вычисления длин максиминных путей между заданными парами вершин графа, Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Высшая школа экономики».

Ссылка на репозиторий С^^Ь:

https://github.com/Kirundel/PHD/tree/main/MSTBPP

4. Свидетельство о государственной регистрации программы для ЭВМ №2024691517 от 9.01.2025: Программа для эффективного анализа чувствительности данных онлайновой задачи о максиминном пути, Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Высшая школа экономики».

Ссылка на репозиторий С^НиЬ:

https://github.com/Kirundel/PHD/tree/main/SensitivityAnalysis

Автор работы выражает глубокую признательность своему научному руководителю д.ф.-м.н., проф. Дмитрию Сергеевичу Малышеву за постоянное внимание к работе, полезные советы и замечания.

Глава 1

Рассматриваемые задачи и начальное алгоритмическое обеспечение

В первой главе приводятся постановки рассматриваемых задач вычислительной геометрии и комбинаторной оптимизации, а также некоторое предварительное алгоритмическое обеспечение, которое будет использоваться в последующих главах настоящей диссертации.

1.1 Формулировки рассматриваемых задач

1.1.1 Задача о к-ом порядковом расстоянии в системе точек единичного квадрата по ^//^-норме

Для заданных Р = (р1?...,рп) — набора точек единичного квадрата и числа 1 ^ к ^ (П) рассматривается следующая задача:

min^ 1(||s < d*) ^ k,

dk . .

где i — индикаторная функция и s £ {1, то}.

Напомним, что /i-норма Минковского между точками p,p' £ r2 определяется как

||p,p'|1 = |Px - pX + |Py - рУ |,

а /то-норма Чебышева между ними определяется как

||p,p'||TO = max (|px - pXI, IPy - рУI)• 18

В диссертации для любых б > 0 и 1 ^ k ^ Q) предлагается б-приближенный алгоритм со сложностью O(n log n log 1) для вычисления значения dk. Иными словами, он возвращает такие конкретные значения dlke и dke, что выполнено

dk - б < dk , е < dk < dk , е < dk + б и работает за время O(n log n log 1).

1.1.2 Задача о минимальном остовном дереве на точках пространства в ¿!-норме

Задача о минимальном остовном дереве (кратко, ЗМОД) для заданного связного взвешенного по ребрам графа состоит в том, чтобы найти в нем остовное дерево, т.е. связный ациклический подграф, содержащий все вершины графа, с минимальной суммой весов его ребер. В диссертации эта задача рассматривается на заданной системе P из n точек пространства Rd с ^-расстоянием между точками. Для любого фиксированного d для решения этой задачи в диссертации предлагается алгоритм сложности O(n logd-1 n).

1.1.3 Задачи о максиминных путях

Задача о максиминном пути (кратко, ЗМП) для заданных связного графа G = (V, E), пропускных способностей его ребер с : E —> r^0 и вершин s, t € V найти

b(s,t) = max min c(e) или arg max min c(e),

P€Pst e€P °P€Pst e€P

где Pst обозначает множество всех путей между s и t. В онлайновой задаче о максиминном пути (кратко, ОЗМП) предполагается, что граф (G, с) известен заранее, а пары (s,t) поступают онлайн. В диссертации предлагается онлайновый алгоритм с временем предобработки O(m+n log n) графа (G, с) и временем O(logn) обработки каждого запроса (s,t). Задача о k максиминных путях (кратко, k-ЗМП) состоит для заданных (G, с) и пар (s1, t1),..., (sk, tk)

в том, чтобы найти b(si,ti) для любого i £ [к]. Этот алгоритм решения ОЗМП сразу дает алгоритм сложности O(m + (n + к) logn) для решения к-ЗМП. В диссертации для решения задачи к-ЗМП предлагается альтернативный оффлайновый алгоритм с тем же ожидаемым временем работы.

1.1.4 Вопросы чувствительности оптимальных решений в онлайновой задаче о максиминном пути

Пусть P* — произвольный максиминный st-путь графа (G, с), а e — произвольное ребро G. Верхним допуском * (e) (нижним допуском 1р* (e)) ребра e относительно P* называется супремум тех чисел а ^ 0, что P* остается максиминным st-путем в графе (G,c+a) (в графе (G,c_a)), где

c±a(e') = c(e') Ve' = e, c+a(e) = c(e) + a, c_a(e) = c(e) _ а.

В диссертации предлагается алгоритм сложности O(ma(m,n)) для предобработки заранее заданных графа (G, с), где c(e1) = c(e2) Ve1 = e2, и его вершин s, t, при помощи которой за константное время можно вычислить верхние и нижние допуски произвольного ребра относительно некоторого максимин-ного st-пути.

1.2 Предварительное алгоритмическое обеспечение

1.2.1 Бинарный поиск

Бинарный поиск — это алгоритм поиска объекта по заданному признаку в множестве объектов, упорядоченных по тому же самому признаку, работающий за логарифмическое время (см., например, [29]). Он заключается в том, что на каждом шаге множество объектов делится на две части и в работе остается та часть множества, где находится искомый объект.

1.2.2 Метод сканирующей гиперплоскости

Метод сканирующей гиперплоскости — это способ обработки заданной системы точек пространства, состоящий в их упорядочивании по какому-нибудь

критерию (или каких-нибудь событий, ассоциированных с точками) и последующем проходе по ним. Например, в известном алгоритме Бентли-Оттмана [16] для поиска всех пар пересекающихся среди заданных отрезков на плоскости такими событиями являются «начало отрезка», «конец отрезка» и «пересечение отрезков». Это позволяет найти все пары пересекающихся отрезков среди n заданных на плоскости за время O(n log n+k), где k — количество пар пересекающихся отрезков, что лучше при не очень больших k, чем наивный переборный алгоритм сложности 0(n2).

1.2.3 Деревья отрезков и Фенвика

Предположим, что задан некоторый числовой массив A[1,..., n]. Требуется так предобработать этот массив, чтобы по результату предобработки T за время O(logn):

1. для каждых заранее неизвестных 1 ^ i ^ n и val Е r перестраивать T после присваивания A[i] := val,

2. для каждого заранее неизвестного запроса 1 ^ i ^ j ^ n вычислять значение суммы

A[i]+ A[i + 1] + ... + A[j ].

Для решения поставленной задачи можно использовать дерево отрезков [29] c дополнительной памятью/временем предобработки O(n) или дерево Фенвика [38] с дополнительной памятью O(n) и временем предобработки O(n log n).

1.2.4 Система непересекающихся множеств

Структура данных «Система Непересекающихся Множеств» (сокращенно СНМ) хранит разбиение некоторого конечного множества на непересекающиеся его подмножества. Она поддерживает операции добавления синглетонов — одноэлементных подмножеств, замены двух подмножеств их объединением и поиска канонического элемента подмножества:

• Сгеа£е(х) — создание синглетона {х} и добавление его к СНМ,

• ^т^(х) — поиск канонического элемента того подмножества, которое содержит х,

• </от(х,у) — замена двух подмножеств с каноническими элементами х и у их объединением.

СНМ обычно реализуется как лес из непересекающихся подмножеств, позволяющий выполнять три основные операции практически за единичное время, см. [42, 50, 75]. Точнее, вставка и объединение в худшем случае выполняются за время 0(1), а поиск выполняется за амортизированное время, ограниченное сверху значением обратной функции Аккермана.

СНМ играют важную роль в эффективной реализации алгоритма Краскала [29] для решения ЗМОД или ее тах-варианта. А именно, на каждом шаге этого алгоритма СНМ хранит (монотонно растущий) лес, который всегда является частью минимального/максимального остовного дерева, полученного после последнего шага. Сначала алгоритм Краскала сортирует ребра по их весам (по неубыванию для ЗМОД или по невозрастанию для ее тах-варианта), затем он сканирует отсортированное множество ребер и определяет, а можно ли добавить текущее ребро к оптимальному решению или нет. Эта проверка основана на операциях объединения и поиска в СНМ. Подобную технику мы будем использовать в оффлайновом алгоритме решения к-ЗМП и в предобработке данных для вычисления верхних/нижних допусков ребер в ОЗМП.

1.2.5 Наименьший общий предок

Пусть Т = (V, Е) — некоторое дерево, в котором выбран корень г £ V. Тем самым, в дереве Т возникает отношение «предок-потомок». Предполагается, что каждая вершина является потомком самой себя. Наименьшим общим предком вершин х,у £ V, обозначаемым через ЬСА(х,у), называется ближайшая к г вершина, для которой х и у одновременно являются потомка-

ми. В работе [15] был предложен алгоритм вычисления наименьшего общего предка любых двух вершин T за время O(log n) при предобработке за время O(n logn). Это так называемый jump-pointers алгоритм, который для каждой вершины x Е V организует ссылки от x к ее предкам, которые расположены от x на расстояниях, равных степеням двойки. Предполагая, что T является взвешенным по ребрам, в работе [3] этот алгоритм был доработан так, чтобы для любых x,y Е V вычислять ребро минимального или максимального веса на пути T(x,y) между x и y в дереве T. Эта доработка здесь явно не описывается, она представлена в приложении.

В работе [36] был предложен алгоритм вычисления наименьшего общего предка любых двух вершин за время O(1) при предобработке за время O(n). К сожалению, не очевидно, каким образом доработать этот алгоритм так, чтобы он вычислял за время o(log n) числовые функции на путях в T.

Пусть T = (V, E) — произвольное дерево. Выберем произвольную вершину r в качестве его корня. Для произвольных s,t Е V и e = xy Е E принадлежность e пути T(s,t) распознается за время O(1) при O(n) предобработке, где n = |V |. Для этого будем использовать алгоритм из [36].

Поиском в ширину от вершины r за время O(n) вычислим глубины всех вершин в T, где глубина |T(r, z)| вершины z обозначается через d(z). Можно считать, что d(y) = d(x) + 1. Обозначим через Tx и Ty компоненты связности леса T\{e}, которые, соответственно, содержат вершины x и y. Тогда r Е Tx. Ясно, что xy Е T(s, t) тогда и только тогда, когда s и t лежат в разных компонентах леса T\{e}. Проверка того, что вершина z Е {s, t} принадлежит Ty, выполняется проверкой LCA(z,y) = y .В точности одна из вершин s и t должна обладать этим свойством.

Глава 2

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

Во второй главе данной диссертации рассматриваются задачи о к-ом порядковом расстоянии на n заданных точках единичного квадрата в /1-норме и о минимальном остовном дереве на n точках d-мерного пространства в /1-норме. При любом 1 ^ k ^ Q) для е-приближенного решения первой задачи предлагается алгоритм сложности O(n log n log1), а для решения второй задачи при каждом фиксированном d предлагается алгоритм сложности O(nlogd-1 n). Эти результаты опубликованы в работах [1, 5].

2.1 Приближенный поиск k-ого порядкового расстояния на точках единичного квадрата в /1//то-норме

2.1.1 Линейное сведение задачи для /i-нормы к задаче для /^-нормы

Напомним, что ^-расстояние между точками а и b на плоскости определяется как

11а, b11 = |ах _ Ьг| + |ау _ by|, что можно переписать следующим образом:

|а, by1 = <

аж + ау — bx — by, аж > bx и ау > by,

—аж + ау + bx — by, аж < bx и ау > by,

аж — ау — bx + by, ах > bx и ау < by,

—ах — ау + bx + by, аx < bx и ау < by,

или

||а,6||1 = тах (|(ах - + («у - Ьу)|, |(&* - «х) + К - Ьу)|).

Рассмотрим преобразование поворотной гомотетии — поворот на 4 с последующим растяжением на

Р = = ( 1 Л М = ( + Ру

\-1 V Ы/ \-Рх + Ру,

px = Px + Ру, РУ = —Px + Ру. После преобразования точка а перейдет в точку а', а точка b перейдет в точку b'. Нетрудно видеть, что выполнены равенства

||а, by1 = max (|аX — bx|, |ау — by|) = ||а', b'||TO.

Отсюда следует, что задача для /1-нормы сводится за линейное время к той же задаче для /то-нормы. Поэтому всюду далее мы будем рассматривать задачу только для /то-нормы. Линиями уровня этой нормы являются квадраты.

2.1.2 Бинарный поиск по мощности покрытия квадратами

Для набора точек P определим на [0,1] функцию

/р(t) = ^ i(||Pi,PjIU ^ t).

Иными словами, /р(t) — это удвоенное количество точек из P, покрываемых квадратами размера 2t с центрами в элементах P, не считая центров самих

квадратов. Нас интересует поиск такого минимального dk, что выполнено неравенство fP(dk) ^ 2k.

Если имеется алгоритм, который вычисляет значение fp(•) в любой точке отрезка [0,1] за время O(T), то е-приближенный поиск точки dk может быть организован за время O(T log i) бинарным поиском. На каждой его итерации выполняется дихотомическое деление текущего отрезка, содержащего dk, сравнение значения fp(•) в его середине mid с 2k, выбор первой половины отрезка, если fP(mid) > 2k, или второй половины, если fP(mid) ^ 2k. Процесс повторяется до тех пор, пока текущий отрезок не станет достаточно маленьким.

Далее будет показано, что значение функции fP(•) в каждой точке отрезка [0,1] вычисляется за время O(nlogn), т.е. что T = O(nlogn). Поэтому е-приближенный алгоритм вычисления dk имеет сложность O(nlognlog 1).

2.1.3 Применение метода сканирующей гиперплоскости

Для нашей задачи точки из P* = P+t U P U P-t, где t Е [0,1] и

P±t = (pi ± t,p2 ± t,...,Pn ± t),

упорядочиваются по неубыванию значения их абсцисс, причем для одинакового значения абсциссы сначала идут точки из P+t, затем точки из P, а затем точки из P-t. Тем самым, каждое из трех типов событий «открытие квадрата», «центр квадрата» и «закрытие квадрата» имеет свой уникальный номер от 1 до 3n и, наоборот, каждому такому номеру соответствует свое событие относительно некоторого квадрата с центром в точке из P.

2.1.4 Описание алгоритма и вывод оценки его трудоемкости

Основная идея нашего алгоритма похожа на основную идею алгоритма Бентли-Оттмана. Мы используем метод сканирующей прямой по оси абсцисс и поддерживаем события «открытие квадрата»/«закрытие квадрата» с помощью массива, индексы которого соответствуют точкам из P. Мощность

покрытия квадратами вычисляется при наступлении событий «центр квадрата» с помощью бинарного поиска соответствующего интервала в индексах массива и отклика дерева отрезков/Фенвика запросом суммы элементов массива с индексами на этом интервале.

В целом, наш алгоритм сложности O(n log n log i) выглядит следующим образом:

Шаг 1. Если рассматривается 11-норма, то перейти к 1то-норме путем поворота направо на | с последующим растяжением на \/2:

(1 Л

Ур Е P вычислить р :=

V-1 V

Шаг 2. Положить dk е := 0,dk е := 1. Пока выполнено dk е — dk е > 2е применять следующие действия:

Шаг 2.1. Для текущей оценки [dk е, dk е] величины dk найти множество

P* := P+t и P U P—t,

dr +d'

где t := fc'£ 2 fc'£. Создать массив Ap из нулей, индексы которого соответ-

ствуют значениям ординат точек из Р, упорядоченных по неубыванию. По массиву Ар построить соответствующее дерево отрезков/дерево Фенвика Тр. Положить счетчик к' мощности покрытия квадратами равным нулю, т.е. к' := 0.

Шаг 2.2. Упорядочить Р* по неубыванию значений абсцисс и сформировать массив из 3п соответствующих событий. Каждое из них хранит соответствующую точку из Р и информацию об одном из трех типов событий («открытие квадрата» или «центр квадрата» или «закрытие квадрата»).

Шаг 2.3. Итерируясь по Р*:

Шаг 2.3.1. Для каждого события «открытие квадрата» с центром в точке р выполнить присваивание Ар [р.у] := Ар [р.у] +1 и перестроить дерево Тр.

Шаг 2.3.2. Для каждого события «закрытие квадрата» с центром в точке p выполнить присваивание Ap [p.y] := Ap [p.y] — 1 и перестроить дерево Tp.

Шаг 2.3.3. Для каждого события «центр квадрата» найти бинарным поиском по индексам массива Ap такой минимальный индекс /р, что py — t ^ /р, и такой максимальный индекс rp, что rp ^ py + t. Затем сделать запрос по дереву Tp: вернуть Sp — сумму элементов Ap с /р-ого по гр-й и выполнить k ^ + Sp 1.

Шаг 2.4. Если k' > 2k, то положить dk е := dk е и dk е := dk'£+ d'k'e. В противном случае положить dk е := k'£2 к'е и dk е := dk е.

Шаг 3. Вернуть dk е и dk е.

Оценим вычислительную сложность каждого из Шагов. Ясно, что Шаг 1 выполняется за время O(n), а Шаг 3 выполняется за время O(1). Количество итераций бинарного поиска Шага 2 можно оценить сверху как |log2 (2^)]. Шаг 2.1 имеет сложность O(n), а шаг 2.2 имеет сложность O(n log n). Каждый из Шагов 2.3.1-2.3.3 имеет сложность O(log n), следовательно, Шаг 2.3 имеет сложность O(n log n). Шаг 2.4 имеет сложность O(1). Таким образом, итоговая сложность нашего алгоритма есть O(n log n log 1).

2.1.5 Вычислительные эксперименты

С целью верификации предложенного алгорит-

ма была выполнена его программная реализация (см. https://github.com/Kirundel/PHD/tree/main/KthMD), а также были проведены вычислительные эксперименты на машине с 4-ядерным процессором Intel Core i7-7700hq с частотой 2.8 гигагерц и оперативной памятью 24 гигабайта. Алгоритм тестировался по критериям правильности его работы и соответствия времени работы теоретическим оценкам сложности.

Для верификации по первому критерию были взяты точки (0, 0), (3,0), (0, 2), (2,3) и значение k = 5 (заметим, что для целочислен-

ных точек алгоритм при 1 > е > 0 выдает точное значение ^), для которых был получен правильный ответ ^ = 5:

§ Microsoft Visual Studio Debut X +

I)S

C:\WorlAPHD\KthMD\x64\Debiig\KthMD.exe (process 6528) exited with code 0. Press any key to close this window ...

Рис. 2.1: Скриншот работы программы на небольших данных

Для верификации по второму критерию независимо друг от друга псевдослучайным образом генерировались n = 2power двумерных точек с равномерным распределением в [0,1] по каждой координате, где 5 ^ power ^ 15, и брались k = 102 и k = 104 и е = 10—5. Эксперименты показали следующие результаты:

-1-1-1-1-Г-

6 8 10 12 14

Двоичный логарифм числа точек

Рис. 2.2: Графики отношения времени работы алгоритма к п log2 п

Эксперименты подтверждают для тестовых данных как правильность работы алгоритма, так и соответствие времени его работы теоретическим оценкам сложности.

2.2 Вычисление МОД на пространственных точках в /1-норме

В этом разделе диссертации предполагается, что d является фиксированным.

2.2.1 Свойство близости и его значение

В основе многих алгоритмов решения геометрических ЗМОД лежит следующая идея — каким-нибудь образом построить разреженный надграф МОД заданных точек, а затем вызвать эффективный алгоритм решения полученной разреженной ЗМОД, например, алгоритм Шазелла или алгоритм Прима. Время работы такого рода алгоритма есть

O(T(n,m) + ma(m,n)) или O(T(n,m) + m + nlogn),

где T(n,m) — время построения надграфа МОД. Способ построения данных надграфов был предложен в работе [80], причем для p = 2 в качестве этого надграфа может выступать триангуляция Делоне (см., например, [6, 31]).

Всюду далее точки x пространства Rd и их координаты x связываются так: x = (x1,..., Xd). Способ из [80] основан на покрытии (относительно заданных точки s и нормы ||-, -||) пространства Rd областями R1,... , Rk(s), где:

• s принадлежит всем этим областям,

• каждая из областей обладает свойством близости (относительно s) — для любых точек p, q £ R^ выполнено ||p, q|| ^ max (||s, p||, ||s, q||).

В [80] (см. Теорему 3.2 той работы) было показано, что для любого конечного множества V точек совокупность всех ребер вида ss^, где s £ V и s^ — ближайший по ||-, - || сосед s в R^ \ {s}, порождает надграф некоторого оптимального решения ЗМОД на V с не более чем ^ k(s) ребрами. Конкретные

Список литературы диссертационного исследования кандидат наук Каймаков Кирилл Владимирович, 2025 год

Литература

[1] Каймаков К. В., Малышев Д. С. Приближенный поиск k-ого порядкового расстояния в системе точек единичного квадрата // Математические заметки. 2024. Т. 116, № 4. C. 502-507.

[2] Каймаков К. В., Малышев Д. С. Эффективное вычисление всех допусков в разреженной задаче о максиминном пути // Успехи математических наук. 2024. Т. 79, № 5. С. 203-204.

[3] Kaymakov K. V., Malyshev D. S. On efficient algorithms for bottleneck path problems with many sources // Optimization Letters. 2024. Vol. 18. P. 12731283.

[4] Kaymakov K.V., Malyshev D.S. Efficient online sensitivity analysis for the injective bottleneck path problem // Optimization Letters. 2024, accepted, doi: 10.1007/s11590-024-02170-5.

[5] Каймаков К. В., Малышев Д. С. Эффективный поиск минимального дерева на точках пространства в li-норме // Математические Заметки. 2025. Т. 117, № 6, принята в печать.

[6] Agarwal P., Edelsbrunner H., Schwarzkopf O., Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs // Discrete and Computational Geometry. 1991. Vol. 6, №1. P. 407-422.

[7] Aho A., Hopcroft J., Ullman J. On finding lowest common ancestors in trees // Proceedings of the 5th Annual ACM Symposium on Theory of Computing. 1973. P. 253-265.

[8] Aissi H., Bazgan C., Vanderpooten D. Min-max and min-max regret versions of combinatorial optimization problems: a survey // European Journal of Operational Research. 2009. Vol. 197, №2. P. 427-438.

[9] Applegate D., Cook W., Dash S., Rohe A. Solution of a min-max vehicle routing problem // INFORMS Journal on Computing. 2002. Vol. 14, №2. P. 132-143.

[10] Asano T., Bhattacharya B., Keil M., Yao Y. On the history of the minimum spanning tree problem // Proceedings of the 4th annual symposium on computational geometry. 1988. P. 252-257.

[11] Aumiiller M., Ceccarello M. Solving k-closest pairs in high-dimensional data // Similarity Search and Applications. 2023. P. 200-214.

[12] Aumiiller M., Dietzfelbinger M., Woelfel P. Explicit and efficient hash families suffice for cuckoo hashing with a stash // Algorithmica. 2014. Vol. 70. 428456.

[13] Baier G., Kohler E., Skutella M. On the k-splittable flow problem // Proceedings of European Symposium on Algorithms. 2002. P. 101-113.

[14] Batsyn M., Goldengorin B., Kocheturov A., Pardalos P. Tolerance-based versus cost-based branchng for the asymmetric capacitated vehicle routing problem. Proceedings of the Second International Conference on Network Analysis. 2012. P. 1-10.

[15] Bender M., Farach-Colton M. The level ancestor problem simplified // Theoretical Computer Science. 2004. Vol. 321, №1. P. 5-12.

[16] Bentley J., Ottman T. Algorithms for reporting and counting geometric intersections // IEEE Transactions on Computers. 1979. Vol. C-28, №9. P. 643-647.

[17] Berkman O., Vishkin U. Recursive star-tree parallel data structure // SIAM Journal on Computing. 1993. Vol. 22, №2. P. 221-242.

[18] Bespamyatnikh S. An optimal algorithm for closest-pair maintenance // Discrete and Computational Geometry. 1998. Vol. 19. P. 175-195.

[19] Booth H., Westbrook J. A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs // Algorithmica. 1994. Vol. 11. P. 341-352.

[20] Boruvka O. About a certain minimal problem // Proceedings of the Moravian Society of Natural Sciences. 1926. Vol. 3, №3. P. 37-58.

[21] Burkard R., Dell'Amico M., Martello S. Assignment problems. 2009.

[22] Camerini P. The min-max spanning tree problem and some extensions // Information Processing Letters. 1978. Vol. 7, №1. P. 10-14.

[23] Chazelle B. A minimum spanning tree algorithm with inverse-Ackermann type complexity // Journal of ACM. 2000. Vol. 47, №6. P. 1028-1047.

[24] Chechik S. et al. Bottleneck paths and trees and deterministic graphical games // Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science. 2016. 27:1-27:13.

[25] Cherkassky B., Goldberg A., Radzik T. Shortest paths algorithms: theory and experimental evaluation // Mathematical Programming, Series A. 1996. Vol. 73. P. 129-174.

[26] Chin F., Houck D. Algorithms for updating minimal spanning trees // Journal of Computer and System Sciences. 1978. Vol. 16, №3. 333-344.

[27] Clarkson K. Fast algorithms for the all nearest neighbors problem // Proceedings of 24th Annual Symposium on Foundations of Computer Science. 1983. P. 226-232.

[28] Corall A., Manolopoulos A., Theodoridis Y., Vassilakopoulos M. Closest pair queries in spatial databases // ACM SIGMOD Record. 2000. Vol. 29, №2. P. 189-200.

[29] Cormen T., Leiserson C., Rivest R., Stein C. Introduction to algorithms: Fourth Edition. 2022.

[30] Dell'Amico M., Toth P. Algorithms and codes for dense assignment problems: the state of the art // Discrete Applied Mathematics. 2004. Vol. 140, №1-2. P. 17-48.

[31] Devillers O. Randomization yields simple O(n log^ n) algorithms for difficult Q(n) problems // International Journal of Computational Geometry and Applications. 1991. Vol. 2, №1. P. 97-111.

[32] Dixon B., Rauch M., Tarjan R. Verification and sensitivity analysis of minimum spanning trees in linear time // SIAM Journal on Computing. 1992. Vol. 21, №6. P. 1184-1192.

[33] Duan R., Lyu K., Xie Y. Single-source bottleneck path algorithm faster than sorting for sparse graphs // Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. 2018. 43:1-43:14.

[34] Duan R., Pettie S. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths // Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2009. P. 384-391.

[35] Edmonds J., Karp R. Theoretical improvements in algorithmic efficiency for network flow problems // Journal of ACM. 1972. Vol. 19, №2. P. 284-264.

[36] Fischer J., Heun V.: Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE // Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching. 2006. P. 36-48.

[37] Felzenszwalb P., Huttenlocher D. Efficient graph-based image segmentation // International Journal of Computer Vision. 2004. Vol. 59, №2. P. 167-181.

[38] Fenwick P. A new data structure for cumulative frequency tables // Software: Practice and Experience. 1994. Vol. 24, №3. P. 327-336.

[39] Fortune S., Hopcroft J. A note on Rabin's nearest-neighbor algorithm // Information Processing Letters. 1979. Vol. 8, №1. P. 20-23.

[40] Fredman M., Tarjan R. Fibonacci heaps and their uses in improved network optimization algorithms // Journal of ACM. 1987. Vol. 34, №3. 596-615.

[41] Gabow H., Bentley J., Tarjan R. Scaling and related techniques for geometry problems // Proceedings of the 16th annual symposium on theory of computing. 1984. P. 135-143.

[42] Galler B., Fischer M. An improved equivalence algorithm // Communications of the ACM. 1964. Vol. 7, №5. P. 301-303.

[43] Germs R., Goldengorin B., Turkensteen M. Lower tolerance-based branch and bound algorithms for the ATSP // Computers and Operations Research.

2012. Vol. 39, №2. P. 291-298.

[44] Goldengorin B., Jager G., Molitor P. Tolerances applied in combinatorial optimization // Journal of Computer Science. 2006. Vol. 2, №9. P. 716-734.

[45] Goldengorin B., Malyshev D., Pardalos P. Efficient computation of tolerances in weighted independent set problems for trees // Doklady Mathematics.

2013. Vol. 87. P. 368-371.

[46] Goldengorin B., Malyshev D., Pardalos P., Zamaraev V. A tolerance-based heuristic approach for the weighted independent set problem // Journal of Combinatorial Optimization. 2015. Vol. 29. P. 433-450.

[47] Graham R., Hell P. On the history of the minimum spanning tree problem // Annals of the History of Computing. 1985. Vol. 7, №1. P. 43-57.

[48] Guibas L., Stolfi J. On computing all northeast nearest neighbors in the L metric // Information Processing Letters. 1983. Vol. 17, №4. P. 219-223.

[49] Harel D., Tarjan R. Fast algorithms for finding nearest common ancestors // SIAM Journal on Computing. 1984. Vol. 13, №2. P. 338-355.

[50] Hopcroft J., Ullman J. Set merging algorithms // SIAM Journal on Computing. 1973. Vol. 2, №4. P. 294-303.

[51] Jonker R., Volgenant A. Improving the Hungarian assignment algorithm // Operational Research Letters. 1986. Vol. 5, №5. P. 171-175.

[52] Kaibel V., Peinhardt M. On the bottleneck shortest path problem // Tech. rep. 2006. 06-22.

[53] Karger D., Klein P., Tarjan R. A randomized linear-time algorithm for finding minimum spanning trees // Journal of the ACM. 1995. Vol. 42, №2. P. 321329.

[54] Kellerer H., Pferschy U., Pisinger D. Knapsack problems. 2004.

[55] Khuller S., Matias Y. A simple randomized sieve algorithm for the closest-pair problem // Information and Computation. 1995. Vol. 118, №1. P. 34-37.

[56] Kruskal J. On the shortest spanning subtree of a graph and the traveling salesman problem // Proceedings of the American Mathematical Society. 1956. Vol. 7, №1. P. 48-50.

[57] Krznaric D., Levcopoulos C., Nilsson B. Minimum spanning trees in d-dimension // Proceedings of the 5th annual European symposium on algorithms. 1997. P. 341-349.

[58] Kurasawa H., Takasu A., Adachi J. Finding the k-closest pairs in metric spaces // Proceedings of the 1st Workshop on New Trends in Similarity Search. 2011. P. 8-13.

[59] Lenhof H., Smid M. Enumerating the k closest pairs optimally // Proceedings of 33rd Annual Symposium on Foundations of Computer Science. 1992. P. 380-386.

[60] Lenhof H., Smid M. Sequential and parallel algorithms for the k closest pairs problem // International Journal of Computational Geometry and Applications. 1995. Vol. 5, №3. P. 273-285

[61] Ljunggren L. et al. Railway timetabling: a maximum bottleneck path algorithm for finding an additional train path // Public Transport. 2021. Vol. 13. P. 597-623.

[62] Malyshev D., Pardalos P. Efficient computation of tolerances in the weighted independent set problem for some classes of graphs // Doklady Mathematics. 2014. Vol. 89. P. 253-256.

[63] Mantegna R. Hierarchical structure in financial markets // The European Physical Journal B-Condensed Matter and Complex Systems. 1999. Vol. 11, №1. P. 193-197.

[64] Mares M. Two linear time algorithms for MST on minor closed graph classes // Archivum Mathematicum. 2002. Vol. 040, №3. P. 315-320.

[65] Mehlhorn K., Stefan N. Dynamic fractional cascading // Algorithmica. 1990. Vol. 5, №2. P. 215-241.

[66] Ohlsson H. Implementation of low complexity FIR filters using a minimum spanning tree // Proceedings of the 12th IEEE Mediterranean electrotechnical conference. 2004. P. 261-264.

[67] Pettie S. Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time // Journal of Graph Algorithms and Applications. 2015. Vol. 19, №1. P. 375-391.

[68] Prim R. Shortest connection networks and some generalizations // Bell System Technical Journal. 1957. Vol. 36, №6. P. 1389-1401.

[69] Ramaswamy R., Orlin J., Chakravarty N. Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs // Mathematical Programming, Series A. 2005. Vol. 102. P. 355-369.

[70] Shamos M., Hoey D. Closest-point problems // Proceedings of the 16th annual symposium on foundations of computer science. 1975. P. 151-162.

[71] Shier D., Witzgall C. Arc tolerances in minimum-path and network flow problems // Networks. 1980. Vol. 10, №4. P. 277-1980.

[72] Shinn T.-W., Takaoka T. Variations on the bottleneck paths problem // Theoretical Computer Science. 2015. Vol. 575. P. 10-16.

[73] Tarjan R. Sensitivity analysis of minimum spanning trees and shortest path trees // Information Processing Letters. 1982. Vol. 14, №1. P. 30-33.

[74] Tarjan R. Data structures and network agorithms. 1983.

[75] Tarjan R., van Leeuwen J. Worst-case analysis of set union algorithms // Journal of the ACM. 1984. Vol. 31, №2. P. 245-281.

[76] Turkensteen M., Ghosh D., Goldengorin B., Sierksma G. Tolerance-based branch and bound algorithms for the ATSP // European Journal of Operational Research. 2008. Vol. 189, №3. P. 775-788.

[77] Turkensteen M., Jager G. Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems // Theoretical Computer Science. 2022. Vol. 937. P. 1-21.

[78] Turkensteen M., Malyshev D., Goldengorin B., Pardalos P. The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems // Journal of Global Optimization. 2017. Vol. 68. 601622.

[79] Vassilevska V., Williams R., Yuster R. All-pairs bottleneck paths for general graphs in truly sub-cubic time // Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 2007. P. 585-589.

[80] Yao A. On constructing minimum spanning trees in k-dimensional spaces and related problem // SIAM Journal on Computing. 1982. Vol. 11, №4. P. 721-736.

[81] Zhou H., Shenoy N., Nicholls W. Efficient minimum spanning tree construction without Delaunay triangulation // Information Processing Letters. 2002. Vol. 81, №5. P. 271-276.

Приложения

Приложение 1: свидетельство о государственной регистрации программы для ЭВМ и код программы для эффективного вычисления заданного порядкового Манхэттенского расстояния между точками на плоскости с данной точностью

ЙКЖАЖ ФШДШРАПЦШШ

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

Ж

■ЩЗ&Ж:;^..

■■ -.....:.......... ....."■-,...... ■ ■ : . ■ ■

Программа для эффектив

№ 2024689963

: : : ...

¡5

) вычисления заданного порядкового Манхэттенского расстояния между точками на плоскости с данной точностью

• автономное

ШШтк

образовательное учреждение высшего образования Национальный исследовательский университет Высшая школа экономики» (Ш)

............„номики» (Ки)

ТТ ■

Авторы: Малышев Дмитрии Сергеевич Кирилл Владимирович (Ки)

.....,..:..,..: . .■■■■■■■ ■ ........ ■

Заявка № 2024688291 Дата поступления 25 ноября 2024 Г.

Дата государственной регистрации

в Реестре программ для ЭВМ 11 декабря 2024 г.

..... ■ ■

тль Федеральной службы собственности

1сдн:эПекгронно

йШМЯН

■

Ю.С. Зубов

Ссылка на репозиторий GitHub: https://github.com/Kirundel/PHD/tree/main/KthMD using namespace std;

#define _CRT_SECURE_NO_WARNINGS #include <vector> #include <map> #include <algorithm>

#include <fstream> ifstream cin("input.txt"); ofstream cout("output.txt");

using ll = long long; using pii = pair<int, int>;

template <typename T>

inline void sort(vector<T>& x) {

sort(x.begin(), x.end());

}

template <typename T>

inline void unique(vector<T>& x) {

sort(x);

auto end_s = unique(x.begin(), x.end()) - x.begin(); x.resize(end_s);

}

struct fenwick_tree {

vector<ll> a;

fenwick_tree(int n) : a(n + 2) {}

void add(int pos, ll delta) {

for (pos++; pos < a.size(); pos += pos & -pos) a[pos] += delta;

}

ll get_sum(int pos)

ll sum = 0;

for (pos++; pos > 0; pos -= pos & -pos)

sum += a[pos]; return sum;

}

ll get_sum(int l, int r) {

return this->get_sum(r) - this->get_sum(l - 1);

} };

class compression {

public: vector<int> a;

void add_value(ll v) {

a.push_back(v);

}

void compress() {

unique(a);

}

int get_val(int value) {

return lower_bound(a.begin(), a.end(), value) - a.begin();

}

int get_up_val(int value) {

return upper_bound(a.begin(), a.end(), value) - a.begin();

} };

int n, m; ll k;

vector<pii> points; compression b_compression;

map<int, vector<pair<int, pii>>>vectors_merge_map; template<typename T>

vector<T>& merge(vector<T>& first_vector, vector<T>& second_vector) {

vector<T>& result_vector =

=vectors_merge_map[first_vector.size() + second_vector.size()];

int l = 0, r = 0;

while (l < first_vector.size() || r < second_vector.size()) {

if (l >= first_vector.size()) {

result_vector[l + r] = second_vector[r]; r++;

}

else {

if (r >= second_vector.size()) {

result_vector[l + r] = first_vector[l]; l++;

}

else {

if (first_vector[l] < second_vector[r]) {

result_vector[l + r] = first_vector[l]; l++;

}

else {

result_vector[l + r] = second_vector[r]; r++;

}

}

}

}

return result_vector;

}

vector<pair<int, vector<pair<int, vector<pair<int,

pii>> events_0; pii>> events_1; pii>> events_2;

ll count_with_length(int deltas) {

for (int i = 0; i < points.size(); i++) {

auto& p = points[i];

events_0[i] = { p.first - deltas, { 0, p.second } }; events_1[i] = { p.first + deltas +1, {1 , p.second } }; events_2[i] = { p.first, { 2 , p.second } };

}

auto& events_t = merge(events_0, events_1); auto& events = merge(events_t, events_2);

fenwick_tree fwt(b_compression.a.size() + 3);

ll answer = 0;

for (auto ev : events) {

int event_y_coord = ev.second.second; int event_type = ev.second.first;

if (event_type == 2) {

int left = b_compression.get_val(event_y_coord - deltas);

int right = b_compression.get_up_val(event_y_coord + deltas) - 1;

answer += fwt.get_sum(left, right) - 1;

}

else {

event_y_coord = b_compression.get_val(event_y_coord);

if (event_type == 0) {

fwt.add(event_y_coord, 1);

}

if (event_type == 1) {

fwt.add(event_y_coord, -1);

}

}

}

return answer / 2;

void init() {

vectors_merge_map[2 * n] vectors_merge_map[3 * n] events_0.resize(n); events_1.resize(n); events_2.resize(n);

}

void solve() {

cin >> n >> k; init();

for (int i = 0; i < n; i++) {

int x, y;

cin >> x >> y;

int a = x + y;

int b = y - x;

points.push_back({ a, b });

b_compression.add_value(b);

}

sort(points);

b_compression.compress();

int left = -1; int right = 4e8 + 1;

while (right - left > 1) {

int mid = (left + right) / 2;

if (count_with_length(mid) < k) {

left = mid;

}

else {

= vector<pair<int, pii>>(2 * n); = vector<pair<int, pii>>(3 * n);

right = mid;

}

cout << right << endl;

}

int main() {

solve(); return 0;

}

Приложение 2: свидетельство о государственной регистрации программы для ЭВМ и код программы для эффективного поиска минимального дерева на точках трехмерного пространства в Манхэттенской норме

пёмж&ж «дшращшш

ш ж т ж

ж

ШШ-о*.,,. ............ .

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2024691203

Ж®/:?

■ :

А \ \ ' ■

..

Программа для эффективного поиска минимального дерева на точках трехмерного пространства в Манхэттенской норме

Правообладатель: федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Высшая школа экономики» (Яи)

.7:':'::'

...

... .....,....

Авторы: Малышев Дмитрий Сергеевич (ЯЦ), Каймаков

ШШШШш

Кирилл Владимирович ^Ц

V V

■ШРР

■

« а §:Ж:ф

Заявка № 2024688270

Дата поступления 25 ноября 2024 Г.

Дата государственной регистрации в Реестре программ для ЭВМ

Руководитель Федеральной службы

по интеллектуальной собственности ш ГО'*-

ДОКУМЕНТ ПОДПИСАН-ЭЙЕКТРОННОИ подписью

Сертификат 0692е7с1о<Й00lpf5Д^!240f670Ьса2026 Ю.С. Зубов

Владелец Зубов Юрий Сергеевич

Действителен с Щ&и по 03.10.2025 _

..;:., Г./:'.:::.:::.;;,;;,

Ссылка на репозиторий GitHub: https://github.com/Kirundel/PHD/tree/main/MST3D_RID

#define _CRT_SECURE_NO_WARNINGS

using namespace std;

#include <vector> #include <fstream> #include <string> #include <algorithm> #include <utility> #include <set> #include <functional> #include <chrono>

ifstream cin("input.txt"); ofstream cout("output.txt");

const int INF = 1000 * 1000 * 1000;

struct PointWithIdx { int x, y, z; int idx;

};

inline int l1_distance(const PointWithIdx& first, const PointWithIdx& second) {

return abs(first.x - second.x) + abs(first.y - second.y) + abs(first.z - second.z);

}

struct Edge {

int distance; int first, second;

Edge() {}

Edge(const PointWithIdx& first, const PointWithIdx& second) : distance(l1_distance(first, second)), first(first.idx), second(second.idx)

{}

bool operator ==(const Edge& other) const {

return min(first, second) == min(other.first, other.second) && max(first, second) == max(other.first, other.second);

};

struct Answer {

long long sum = 0; vector<Edge> edges;

};

class MSTAlgorithm { public:

virtual Answer MST(int n, vector<Edge>& edges) = 0;

};

class MST3DAlgorithm { public:

virtual Answer MST3D(int n, vector<PointWithIdx>& points) = 0;

};

struct SegmentTreeCoreProperties { PointWithIdx queryPoint; PointWithIdx left; PointWithIdx right; vector<int> answer; bool need_clear; long long add_nums = 0; long long erase_nums = 0; long long get_nums = 0;

};

class AdvancedSegmentTree2D { public:

SegmentTreeCoreProperties* coreProperties; int n;

int std_length; vector<pair<int, int>> coord; vector<unique_ptr<set<pair<int, int>>>> sets; vector<bool> is_end_point; vector<int> max_point;

AdvancedSegmentTree2D(SegmentTreeCoreProperties* coreProperties,

vector<PointWithIdx>& points);

void build(

vector<PointWithIdx>& points, vector<pair<int, pair<int, int>>>& vpp, int v, int l, int r);

void add_point(int v);

void remove_point(int v);

inline bool is_intersect(int v);

inline bool is_inner(int v);

inline void get_all_points_query(int v);

void get_all_points(int v);

AdvancedSegmentTree2D::AdvancedSegmentTree2D(SegmentTreeCoreProperties* coreProperties,

vector<PointWithIdx>& points) :

coreProperties(coreProperties)

{

sort(

points.begin(), points.end(),

[](const auto& f, const auto& s) {return f.y < s.y; }

);

vector<pair<int, pair<int, int>>>vpp; vpp.push_back({ points[0].y, {0, 0} }); for (int i = 1; i < points.size(); i++) { if (vpp.back().first == points[i].y) { vpp.back().second.second = i;

}

else {

vpp.push_back({ points[i].y, {i, i} });

}

}

n = vpp.size(); std_length = 4 * n;

coord.resize(std_length, { -INF, INF }); sets.resize(std_length); is_end_point.resize(std_length, false); max_point.resize(std_length, -INF);

build(points, vpp, 1, 0, n - 1);

}

void AdvancedSegmentTree2D::build( vector<PointWithIdx>& points, vector<pair<int, pair<int, int>>>& vpp, int v, int l, int r)

{

coord[v] = { (points.begin() + vpp[l].second.first)->y, (points.begin() + vpp[r].second.second)->y }; if (l >= r) {

is_end_point[v] = true;

sets[v] = make_unique<set<pair<int, int>>>();

}

else {

int mid = (l + r) /2; build(points, vpp, v * 2, l, mid); build(points, vpp, v * 2 + 1, mid + 1, r);

}

}

void AdvancedSegmentTree2D::add_point(int v) { if (!is_end_point[v]) {

if (coord[v * 2].second >= coreProperties->queryPoint.y) { add_point(v * 2);

}

else {

add_point(v * 2 + 1);

}

max_point[v] = max(max_point[v * 2], max_point[v * 2 + 1]);

}

else {

sets[v]->insert({ coreProperties->queryPoint.z, coreProperties->queryPoint.idx }); max_point[v] = max(max_point[v], coreProperties->queryPoint.z);

}

return;

}

void AdvancedSegmentTree2D::remove_point(int v) { if (!is_end_point[v]) {

if (coord[v * 2].second >= coreProperties->queryPoint.y) { remove_point(v * 2);

}

else {

remove_point(v * 2 + 1);

}

max_point[v] = max(max_point[v * 2], max_point[v * 2 + 1]);

}

else {

sets[v]->erase({ coreProperties->queryPoint.z, coreProperties->queryPoint.idx }); if (sets[v]->size() > 0) {

max_point[v] = sets[v]->rbegin()->first;

}

else {

max_point[v] = -INF;

}

}

return;

}

inline bool AdvancedSegmentTree2D::is_intersect(int v) { return coreProperties->left.y <= coord[v].second && coreProperties->right.y >= coord[v].first;

}

inline bool AdvancedSegmentTree2D::is_inner(int v) { return coreProperties->left.y <= coord[v].first && coreProperties->right.y >= coord[v].second;

}

inline void AdvancedSegmentTree2D::get_all_points_query(int v) {

if (is_intersect(v) && max_point[v] >= coreProperties->left.z) { get_all_points(v);

}

}

void AdvancedSegmentTree2D::get_all_points(int v) { if (is_end_point[v] && is_inner(v)) {

for (auto iter = sets[v]->rbegin(); iter != sets[v]->rend(); iter++) { if (iter->first >= coreProperties->left.z) {

coreProperties->answer.push_back(iter->second);

else {

break;

}

}

return;

}

if (!is_end_point[v]) {

get_all_points_query(v * 2); get_all_points_query(v * 2 + 1);

max_point[v] = max(max_point[v * 2], max_point[v * 2 + 1]);

}

}