Максимальный непересекающийся набор

В вычислительной геометрии ( максимальное непересекающееся множество MDS ) — это наибольший набор непересекающихся геометрических фигур, выбранных из заданного набора фигур-кандидатов.

Каждый набор непересекающихся фигур является независимым набором в графе пересечений фигур. Таким образом, проблема MDS является частным случаем проблемы максимального независимого множества (MIS) . Обе задачи являются NP-полными , но найти MDS может быть проще, чем найти MIS, в двух отношениях:

Для общей задачи MIS наиболее известные точные алгоритмы являются экспоненциальными. В некоторых геометрических графах пересечений существуют субэкспоненциальные алгоритмы поиска MDS. ^[1]
Общую задачу MIS трудно аппроксимировать, и она даже не имеет аппроксимации с постоянным коэффициентом. В некоторых геометрических графах пересечений существуют схемы аппроксимации с полиномиальным временем (PTAS) для поиска MDS.

Поиск MDS важен в таких приложениях, как автоматическое размещение меток , проектирование схем СБИС и мультиплексирование с частотным разделением сотовой связи .

Проблему MDS можно обобщить, присвоив каждой фигуре разный вес и найдя непересекающееся множество с максимальным общим весом.

В следующем тексте MDS( C ) обозначает максимальное непересекающееся множество в множестве C .

Жадные алгоритмы

Учитывая набор C фигур, приближение к MDS( C ) можно найти с помощью следующего жадного алгоритма :

ИНИЦИАЛИЗАЦИЯ: Инициализировать пустой набор S .
ПОИСК: Для каждой фигуры xi в C :
1. Вычислите J(xi), подмножество всех фигур в C , которые пересекают xi (включая саму xi ).
2. Присвойте N(xi) количество фигур в J(xi).
3. Выберите любой xj такой, что N(xj) является максимальным, т.е. фигуру, которая касается такого же количества фигур, как и любая другая.
4. Из всех фигур xi, пересекающих xj (включая сам xj), выберите фигуру x, которая касается наименьшего числа других фигур, т. е. x такую, что. N(x) — минимум
Добавьте x к S.
Удалить x из C и удалить J(x) и N(x)
есть фигуры Если в C , вернитесь к поиску.
вернуть набор S. КОНЕЦ :

Для каждой фигуры x , которую мы добавляем в S , мы теряем формы в N(x) , поскольку они пересекаются с x и, следовательно, не могут быть добавлены в S позже. Однако некоторые из этих фигур сами пересекаются, и поэтому в любом случае невозможно, чтобы все они находились в оптимальном решении MDS(S) . Наибольшее подмножество фигур, которое может находиться в оптимальном решении, — это MDS(N(x)) . Следовательно, выбирая x , который минимизирует |MDS(N(x))| минимизирует потери от добавления x к S .

В частности, если мы можем гарантировать, что существует x , для которого |MDS(N(x))| ограничено константой (скажем, M ), то этот жадный алгоритм дает аппроксимацию постоянного M -фактора, поскольку мы можем гарантировать, что:

$|S|\geq {\frac {|MDS(C)|}{M}}$

Такая верхняя оценка M существует для нескольких интересных случаев:

1-мерные интервалы: точный полиномиальный алгоритм

Когда C представляет собой набор интервалов на линии, M = 1, и, таким образом, жадный алгоритм находит точный MDS. Чтобы убедиться в этом, предположим, что интервалы вертикальны, и пусть x — интервал с самой высокой нижней конечной точкой . Все остальные интервалы, пересекаемые x, должны пересекать его нижнюю конечную точку. Следовательно, все интервалы в N(x) пересекаются друг с другом, а MDS(N(x)) размер не превышает 1 (см. рисунок).

Следовательно, в 1-мерном случае МДС можно найти ровно за время O ( n log n ): ^[2]

Отсортируйте интервалы в порядке возрастания их нижних конечных точек (это занимает время O ( n log n )).
Добавьте интервал с самой высокой нижней конечной точкой и удалите все пересекающие его интервалы.
Продолжайте до тех пор, пока не останется интервалов.

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

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

Жирные формы: аппроксимации с постоянным коэффициентом

Когда C — набор единичных дисков, M =3, ^[3] потому что самый левый диск (диск, центр которого имеет наименьшую координату x ) пересекает не более трех других непересекающихся дисков (см. рисунок). Поэтому жадный алгоритм дает 3-приближение, т. е. находит непересекающееся множество размером не менее MDS(C) /3.

Аналогично, когда C представляет собой набор единичных квадратов, параллельных осям, M = 2.

Когда C представляет собой набор дисков произвольного размера, M = 5, поскольку диск наименьшего радиуса пересекает не более 5 других непересекающихся дисков (см. Рисунок).

Аналогично, когда C представляет собой набор квадратов произвольного размера, параллельных осям, M = 4.

Другие константы можно рассчитать для других правильных многоугольников . ^[3]

Алгоритмы «разделяй и властвуй»

Самый распространенный подход к поиску MDS — «разделяй и властвуй». Типичный алгоритм в этом подходе выглядит следующим образом:

Разделите данный набор фигур на два или более подмножества так, чтобы фигуры в каждом подмножестве не могли перекрывать формы в других подмножествах из-за геометрических соображений.
Рекурсивно найдите MDS в каждом подмножестве отдельно.
Верните объединение MDS из всех подмножеств.

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

Оси-параллельные прямоугольники одинаковой высоты: 2-приближение

Пусть C — набор из n прямоугольников, параллельных осям на плоскости, все одинаковой высоты H, но разной длины. Следующий алгоритм находит непересекающееся множество размером не менее |MDS( C )|/2 за время O ( n log n ): ^[2]

Нарисуйте m горизонтальных линий таких, что:
1. Расстояние между двумя строками строго больше, H. чем
2. Каждая линия пересекает хотя бы один прямоугольник (следовательно, m ≤ n ).
3. Каждый прямоугольник пересекает ровно одна прямая.
Поскольку высота всех прямоугольников равна H , прямоугольник не может пересекаться более чем одной линией. Поэтому линии разбивают множество прямоугольников на m подмножеств ( $R_{i},\ldots ,R_{m}$ ) – каждое подмножество включает прямоугольники, пересекаемые одной линией.
Для каждого подмножества $R_{i}$ , вычислите точный MDS $M_{i}$ с использованием одномерного жадного алгоритма (см. выше).
По построению прямоугольники в ( $R_{i}$ $R_{i}$ ) может пересекать только прямоугольники в $R_{i+1}$ $R_{i+1}$ или в $R_{i-1}$ $R_{i-1}$ . Следовательно, каждое из следующих двух объединений представляет собой непересекающиеся множества:
- Союз нечетных МДС: $M_{1}\cup M_{3}\cup \cdots$
- Союз четных МДС: $M_{2}\cup M_{4}\cup \cdots$
Верните самый большой из этих двух союзов. Его размер должен быть не менее |MDS|/2.

Оси-параллельные прямоугольники одинаковой высоты: PTAS

Пусть C — набор из n прямоугольников, параллельных осям на плоскости, одинаковой высоты, но разной длины. Существует алгоритм, который находит непересекающееся множество размером не менее |MDS( C )|/(1 + 1/ k ) за время O ( n ^{2k −1}), для каждой константы k > 1. ^[2]

Алгоритм представляет собой усовершенствование вышеупомянутого 2-приближения за счет объединения динамического программирования с методом сдвига Хохбаума и Маасса. ^[4]

Этот алгоритм можно обобщить на d измерений. Если метки имеют одинаковый размер во всех измерениях, кроме одного, можно найти аналогичное приближение, применив динамическое программирование по одному из измерений. Это также сокращает время до n^O(1/e). ^[5]

Прямоугольники, параллельные осям: аппроксимация логарифмическим коэффициентом

Пусть C — набор из n прямоугольников, параллельных осям, на плоскости. Следующий алгоритм находит непересекающееся множество размером не менее ${\frac {|MDS(C)|}{\log {n}}}$ вовремя $O(n\log {n})$ : ^[2]

ИНИЦИАЛИЗАЦИЯ: отсортируйте горизонтальные края заданных прямоугольников по их координате y , а вертикальные края по их координате x (этот шаг занимает время O ( n log n )).
УСЛОВИЕ ОСТАНОВКИ: Если существует не более n ≤ 2 фигур, вычислите MDS напрямую и вернитесь.
РЕКУРСИВНАЯ ЧАСТЬ:
1. Позволять $x_{\mathrm {med} }$ быть медианной координатой x .
2. Разделите входные прямоугольники на три группы в соответствии с их отношением к линии. $x=x_{\mathrm {med} }$ : те, что полностью слева от него ( $R_{\mathrm {left} }$ ), те, что полностью справа от него ( $R_{\mathrm {right} }$ ), и пересекаемые ею ( $R_{\mathrm {int} }$ ). По построению мощности $R_{\mathrm {left} }$ и $R_{\mathrm {right} }$ не более n /2.
3. Рекурсивно вычислить приблизительный MDS в $R_{\mathrm {left} }$ ( $M_{\mathrm {left} }$ ) и в $R_{\mathrm {right} }$ ( $M_{\mathrm {right} }$ ) и вычислим их объединение. По построению прямоугольники в $M_{\mathrm {left} }$ и $M_{\mathrm {right} }$ все непересекающиеся, поэтому $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ представляет собой непересекающееся множество.
4. Вычислите точный MDS в $R_{\mathrm {int} }$ ( $M_{\mathrm {int} }$ ). Поскольку все прямоугольники в $R_{\mathrm {int} }$ пересекать одну вертикальную линию $x=x_{\mathrm {med} }$ , это вычисление эквивалентно поиску MDS из набора интервалов и может быть решено точно за время O(n log n) (см. выше).
Верните либо $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ или $M_{\mathrm {int} }$ – тот из них, который больше.

По индукции доказывается, что на последнем шаге либо $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ или $M_{\mathrm {int} }$ иметь мощность не менее ${\frac {|MDS(C)|}{\log {n}}}$ .

Чалермсукк и Чузой ^[6] улучшили коэффициент до $O(\log {\log {n}})$ .

Чалермсук и Вальчак ^[7] представили $O(\log {\log {n}})$ -алгоритма приближения к более общей настройке, в которой каждый прямоугольник имеет вес , и цель состоит в том, чтобы найти независимый набор максимального общего веса.

Прямоугольники, параллельные осям: аппроксимация с постоянным коэффициентом

Долгое время было неизвестно, существует ли приближение постоянного коэффициента для прямоугольников, параллельных осям, различной длины и высоты. Было высказано предположение, что такое приближение можно найти с помощью гильотинных разрезов . В частности, если существует гильотинное разделение осей-параллельных прямоугольников, в которых $\Omega (n)$ прямоугольники разделены, то его можно использовать в подходе динамического программирования для нахождения аппроксимации MDS с постоянным коэффициентом. ^[8]^{: под.1.2}

На сегодняшний день неизвестно, существует ли такое гильотинное разделение. Однако существуют алгоритмы аппроксимации с постоянным коэффициентом, использующие негильотинные разрезы:

Джозеф С.Б. Митчелл представил 10-факторный алгоритм аппроксимации. Его алгоритм основан на разбиении плоскости на прямоугольники с обрезанными углами . ^[9]
Гальвес, Хан, Мари, Мёмке, Питту и Визе представили алгоритм, разделяющий плоскость на более общий класс многоугольников. Это упрощает анализ и улучшает аппроксимацию до 6-факторной. Кроме того, они улучшили аппроксимацию до 3-факторной ^[10] а затем к (2+ε)-фактору. ^[11]

Толстые объекты одинакового размера: PTAS

Пусть C — набор из n квадратов или кругов одинакового размера. Хохбаум и Маасс ^[4] представил схему аппроксимации полиномиального времени для поиска MDS с использованием простой стратегии смещенной сетки. Он находит решение в пределах (1 − ε) от максимума за время n ^{О (1/ е ²)} время и линейное пространство. Стратегия распространяется на любую коллекцию толстых объектов примерно одинакового размера (т. е. когда соотношение максимального и минимального размера ограничено константой).

Толстые объекты произвольных размеров: PTAS.

Пусть C — набор из n толстых объектов , таких как квадраты или круги , произвольных размеров. Существует ПТАС для поиска МДС на основе многоуровневого выравнивания сетки. Он был открыт двумя группами примерно в одно и то же время и описан двумя разными способами.

Разделение уровней

Алгоритм Эрлебаха, Янсена и Зейделя. ^[12] находит непересекающееся множество размером не менее (1 − 1/ k ) ² ⋅ |МДС( С )| вовремя н ^{Хорошо ²)}, для каждой константы k > 1. Это работает следующим образом.

Масштабируйте диски так, чтобы диаметр наименьшего диска был равен 1. Разбейте диски на уровни в зависимости от логарифма их размера. Т.е. j -й уровень содержит все диски диаметром между ( k + 1) ^дж и ( к + 1) ^{й +1}, для j ≤ 0 (самый маленький диск находится на уровне 0).

Для каждого уровня j наложите на плоскость сетку, состоящую из линий ( k + 1) ^{й +1} отдельно друг от друга. По построению каждый диск может пересекать не более одной горизонтальной линии и одной вертикальной линии со своего уровня.

Для каждого r , s между 0 и k определите D ( r , s ) как подмножество дисков, которые не пересекаются ни горизонтальной линией, индекс которой по модулю k равен r , ни какой-либо вертикальной линией, модуль индекса k которой равен s . По принципу «ячейки» существует хотя бы одна пара (r,s) такая, что $|\mathrm {MDS} (D(r,s))|\geq (1-{\frac {1}{k}})^{2}\cdot |\mathrm {MDS} |$ , т. е. мы можем найти МДС только в D ( r , s ) и пропустить лишь небольшую часть дисков в оптимальном решении:

Для всех к ² возможные значения r , s (0 ≤ r , s < k ), вычислите D ( r , s ) с помощью динамического программирования .
Вернуть наибольшее из этих k ² наборы.

Сдвинутые квадродеревья

Алгоритм Чана ^[5] находит непересекающееся множество размером не менее (1 − 2/ k )⋅|MDS( C )| вовремя н ^{Хорошо )}, для каждой константы k > 1.

Алгоритм использует сдвинутые деревья квадрантов . Ключевой концепцией алгоритма является выравнивание по сетке дерева квадроциклов. Объект размера r называется k-выровненным (где k ≥ 1 — константа), если он находится внутри ячейки квадродерева размером не более kr ( R ≤ kr ).

По определению, k -выровненный объект, пересекающий границу ячейки квадерева размера R, должен иметь размер не менее R / k ( r > R / k ). Границу ячейки размера R можно покрыть 4k квадратами размера R / k ; следовательно, число непересекающихся жирных объектов, пересекающих границу этой ячейки, не превышает 4 kc , где c — константа, измеряющая жирность объектов.

Следовательно, если все объекты толстые и k -выровнены, можно найти точное максимальное непересекающееся множество за время n. ^{О ( кс )} используя алгоритм «разделяй и властвуй». Начните с ячейки квадродерева, содержащей все объекты. Затем рекурсивно разделите его на меньшие ячейки квадродерева, найдите максимум в каждой меньшей ячейке и объедините результаты, чтобы получить максимум в большей ячейке. Поскольку количество непересекающихся толстых объектов, пересекающих границу каждой ячейки квадродерева, ограничено 4 kc , мы можем просто «угадать», какие объекты пересекают границу в оптимальном решении, а затем применить принцип «разделяй и властвуй» к объектам внутри.

Если почти все объекты выровнены по k , мы можем просто отбросить объекты, которые не выровнены по k , и найти максимальное непересекающееся множество оставшихся объектов за время n. ^{Хорошо )}. Это приводит к аппроксимации (1 - e ), где e — это доля объектов, которые не выровнены по k .

Если большинство объектов не выровнены по k , мы можем попытаться выровнять их k по , сдвигая сетку кратно (1/ k ,1/ k ). Во-первых, масштабируйте объекты так, чтобы все они содержались в единичном квадрате. Затем рассмотрим k сдвигов сетки: (0,0), (1/ k ,1/ k ), (2/ k ,2/ k ), ..., (( k − 1)/ k ,( k - 1)/ к ). Т.е. для каждого j из {0,..., k − 1} рассмотрим сдвиг сетки в (j/k,j/k). Можно доказать, что каждая метка будет 2 k -выровнена по крайней мере для k − 2 значений j . Теперь для каждого j отбросьте объекты, которые не выровнены по k при сдвиге ( j / k , j / k ), и найдите максимальное непересекающееся множество оставшихся объектов. Назовите это множество A ( j ). Назовите реальное максимальное непересекающееся множество A *. Затем:

$\sum _{j=0,\ldots ,k-1}{|A(j)|}\geq (k-2)|A*|$

Следовательно, наибольший A ( j ) имеет размер не менее: (1 − 2/ k )| А *|. Возвращаемое значение алгоритма — наибольшее A ( j ); коэффициент аппроксимации равен (1 − 2/ k ), а время выполнения n ^{Хорошо )}. Мы можем сделать коэффициент аппроксимации настолько маленьким, насколько захотим, так что это PTAS .

Обе версии можно обобщить на размерность d (с разными коэффициентами аппроксимации) и на взвешенный случай.

Алгоритмы геометрического разделителя

Некоторые алгоритмы «разделяй и властвуй» основаны на определенной теореме о геометрическом разделителе . Геометрический разделитель — это линия или фигура, которая разделяет заданный набор фигур на два меньших подмножества, так что количество фигур, потерянных при разделении, относительно невелико. Это позволяет использовать как PTAS , так и субэкспоненциальные точные алгоритмы, как описано ниже.

Толстые объекты произвольных размеров: PTAS с использованием геометрических разделителей

Пусть C — набор из n толстых объектов , таких как квадраты или круги, произвольных размеров. Чан ^[5] Описанный алгоритм находит непересекающееся множество размером не менее (1 − O ( √ b ))⋅|MDS( C )| вовремя н ^{О ( б )}, для каждой константы b > 1.

Алгоритм основан на следующей теореме о геометрическом сепараторе, которую можно доказать аналогично доказательству существования геометрического сепаратора для непересекающихся квадратов :

Для каждого набора C толстых объектов существует прямоугольник, который делит C на три подмножества объектов – C _внутри , C _{снаружи} и C _{на границе} , такие что:

|MDS( C _внутри )| ≤ а |MDS( C )|
|MDS( C _{снаружи} )| ≤ а|MDS( C )|
|MDS( C _{граница} )| с √ | МДС( С ) |

где a и c — константы. Если бы мы могли точно вычислить MDS( C ), мы могли бы сделать константу a всего 2/3, правильно выбрав прямоугольник-разделитель. Но поскольку мы можем аппроксимировать MDS( C ) только постоянным коэффициентом, константа a должна быть больше. К счастью, a остается константой, независимой от | С |.

Эта теорема о сепараторе позволяет построить следующие PTAS:

Выберите константу b . Проверьте все возможные комбинации до b + 1 меток.

Если |MDS( C )| имеет размер не более b (т.е. все наборы меток b + 1 не пересекаются), затем просто верните этот MDS и выйдите. Этот шаг занимает n ^{О ( б )} время.
В противном случае используйте геометрический разделитель, чтобы разделить C на два подмножества. Найдите приблизительный MDS в C _внутри и C _{снаружи} отдельно и верните их комбинацию как приблизительный MDS в C .

Пусть E ( m ) будет ошибкой приведенного выше алгоритма, когда оптимальный размер MDS равен MDS( C ) = m . Когда m ≤ b , ошибка равна 0, поскольку максимальное непересекающееся множество вычисляется точно; когда m > b , ошибка увеличивается не более чем на c √ m — количество меток, пересекаемых разделителем. Худший случай для алгоритма — это когда разделение на каждом шаге имеет максимально возможное соотношение a :(1 − a ). Следовательно, функция ошибок удовлетворяет следующему рекуррентному соотношению:

E(m)=0\ \ \ \ {\text{ if }}m\leq b

E(m)=E(a\cdot m)+E((1-a)\cdot m)+c\cdot {\sqrt {m}}{\text{ if }}m>b

Решение этого повторения:

E(m)=({\frac {0}{b}}+{\frac {c}{{\sqrt {b}}({\sqrt {a}}+{\sqrt {1-a}}-1)}})\cdot m-{\frac {c}{{\sqrt {a}}+{\sqrt {1-a}}-1}}\cdot {\sqrt {m}}.

то есть, $E(m)=O(m/{\sqrt {b}})$ . Мы можем сделать коэффициент аппроксимации настолько малым, насколько захотим, правильно выбрав b .

Этот PTAS более экономичен по пространству, чем PTAS, основанный на квадродеревьях, и может обрабатывать обобщение, при котором объекты могут скользить, но не может обрабатывать взвешенный случай.

Диски с ограниченным соотношением размеров: точный субэкспоненциальный алгоритм

Пусть C — набор из n дисков, такой, что отношение наибольшего радиуса к наименьшему радиусу не превышает r . Следующий алгоритм находит MDS( C ) точно за время. $2^{O(r\cdot {\sqrt {n}})}$ . ^[13]

Алгоритм основан на ограниченном по ширине геометрическом сепараторе на множестве Q центров всех дисков в C . Эта теорема о сепараторе позволяет построить следующий точный алгоритм:

Найдите разделительную линию такую, чтобы не более 2 n /3 центров находились справа от нее ( C _справа ), не более 2 n /3 центров находились слева от нее ( C _слева ) и не более O ( √ n ) центров находились на расстояние менее r /2 от линии ( C _int ).
Рассмотрим все возможные непересекающиеся подмножества C _int . Есть максимум $2^{O(r\cdot {\sqrt {n}})}$ такие подмножества. Для каждого такого подмножества рекурсивно вычислите MDS C _left и MDS C _right и верните наибольший объединенный набор.

Время выполнения этого алгоритма удовлетворяет следующему рекуррентному соотношению:

T(1)=1

T(n)=2^{O(r\cdot {\sqrt {n}})}T\left({\frac {2n}{3}}\right){\text{ if }}n>1

Решение этого повторения:

T(n)=2^{O(r\cdot {\sqrt {n}})}

Алгоритмы локального поиска

Псевдодиски: ПТАС

Псевдодисковый набор — это набор объектов, в котором границы каждой пары объектов пересекаются не более двух раз (обратите внимание, что это определение относится ко всей коллекции и ничего не говорит о формах конкретных объектов в коллекции). ). Множество псевдодисков имеет ограниченную сложность объединения , т. е. количество точек пересечения на границе объединения всех объектов линейно по числу объектов. Например, набор квадратов или кругов произвольных размеров является набором псевдодисков.

Пусть C — набор псевдодисков с n объектами. Алгоритм локального поиска Чана и Хар-Пеледа ^[14] находит непересекающееся множество размера не менее $(1-O({\frac {1}{\sqrt {b}}}))\cdot |MDS(C)|$ вовремя $O(n^{b+3})$ , для каждой целочисленной константы $b\geq 0$ :

ИНИЦИАЛИЗАЦИЯ: Инициализировать пустой набор, $S$ .
ПОИСК: цикл по всем подмножествам $C-S$ $CS$ размер которого находится между 1 и $b+1$ $б+1$ . Для каждого такого подмножества X :
- Убедитесь, что сам X независим (в противном случае перейдите к следующему подмножеству);
- Вычислите набор Y объектов в S, которые пересекают X .
- Если $|Y|<|X|$ , затем удалите Y из S и вставьте X : $S:=S-Y+X$ .
вернуть набор S. КОНЕЦ :

Каждый обмен на этапе поиска увеличивает размер S как минимум на 1 и, следовательно, может произойти не более n раз.

Алгоритм очень прост; трудная часть состоит в том, чтобы доказать коэффициент аппроксимации. ^[14]

См. также. ^[15]

Алгоритмы релаксации линейного программирования

Псевдодиски: ПТАС

Пусть C — множество псевдодисков с n объектами и сложностью объединения u . Используя релаксацию линейного программирования , можно найти непересекающееся множество размером не менее ${\frac {n}{u}}\cdot |MDS(C)|$ . Это возможно либо с помощью рандомизированного алгоритма, который имеет высокую вероятность успеха и время выполнения. $O(n^{3})$ или детерминированный алгоритм с более медленным временем выполнения (но все же полиномиальный). Этот алгоритм можно обобщить на взвешенный случай. ^[14]

Другие классы форм, для которых известны приближения.

Сегменты прямых в двумерной плоскости. ^[15]^[16]
Произвольные двумерные выпуклые объекты . ^[15]
Кривые с ограниченным числом точек пересечения. ^[16]

Внешние ссылки

Примечания

^ Рави, СС; Хант, HB (1987). «Применение теоремы о плоском сепараторе к задачам подсчета». Письма об обработке информации . 25 (5): 317. дои : 10.1016/0020-0190(87)90206-7 . , Смит, В.Д.; Вормальд, Северная Каролина (1998). «Теоремы и приложения о геометрическом сепараторе» . Материалы 39-го ежегодного симпозиума по основам информатики (кат. № 98CB36280) . п. 232. дои : 10.1109/sfcs.1998.743449 . ISBN 978-0-8186-9172-0 . S2CID 17962961 .
^ Jump up to: ^а ^б ^с ^д Агарвал, ПК; Ван Кревелд, М.; Сури, С. (1998). «Размещение этикетки по максимально независимому множеству в прямоугольниках». Вычислительная геометрия . 11 (3–4): 209. doi : 10.1016/s0925-7721(98)00028-5 . hdl : 1874/18908 .
^ Jump up to: ^а ^б Марат, МВ; Бреу, Х.; Хант, HB; Рави, СС; Розенкранц, диджей (1995). «Простые эвристики для единичных дисковых графов». Сети . 25 (2): 59. arXiv : math/9409226 . дои : 10.1002/net.3230250205 .
^ Jump up to: ^а ^б Хохбаум, Д.С. ; Маасс, В. (1985). «Аппроксимационные схемы для задач покрытия и упаковки в обработке изображений и СБИС» . Журнал АКМ . 32 : 130–136. дои : 10.1145/2455.214106 . S2CID 2383627 .
^ Jump up to: ^а ^б ^с Чан, ТМ (2003). «Схемы аппроксимации полиномиального времени для упаковки и прокалывания толстых объектов». Журнал алгоритмов . 46 (2): 178–189. CiteSeerX 10.1.1.21.5344 . дои : 10.1016/s0196-6774(02)00294-8 .
^ Чалермсук, П.; Чужой, Дж. (2009). «Максимально независимый набор прямоугольников». Материалы двадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 892. дои : 10.1137/1.9781611973068.97 . ISBN 978-0-89871-680-1 .
^ Чалермсук, Паринья; Вальчак, Бартош (01 января 2021 г.), «Раскраска и набор прямоугольников, не зависящий от максимального веса», Труды симпозиума ACM-SIAM 2021 года по дискретным алгоритмам (SODA) , Труды Общества промышленной и прикладной математики, стр. 860– 868, arXiv : 2007.07880 , doi : 10.1137/1.9781611976465.54 , ISBN 978-1-61197-646-5 , S2CID 220525811
^ Абед, Фидаа; Чалермсук, Паринья; Корреа, Хосе; Карренбауэр, Андреас; Перес-Лантеро, Пабло; Сото, Хосе А.; Визе, Андреас (2015). О последовательности гильотинной резки . стр. 1–19. doi : 10.4230/LIPIcs.APPROX-RANDOM.2015.1 . ISBN 978-3-939897-89-7 .
^ Митчелл, Джозеф С.Б. (25 июня 2021 г.). «Аппроксимация максимального независимого множества для прямоугольников на плоскости». arXiv : 2101.00326 [ cs.CG ].
^ Гальвес, Уолдо; Хан, Ариндам; Мари, Матье; Мёмке, Тобиас; Питту, Мадхусудхан Редди; Визе, Андреас (01 января 2022 г.), «Алгоритм с тремя приближениями для максимального независимого набора прямоугольников» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2022 г. , Труды Общества промышленной и прикладной математики, стр. 894–905, doi : 10.1137/1.9781611977073.38 , ISBN. 978-1-61197-707-3 , S2CID 235265867 , получено 29 сентября 2022 г.
^ Гальвез, Уолдо; Хан, Ариндам; Муж Мэтью; Мёмке, Тобиас; Редди, Мадхусудхан; Визе, Андреас (26 сентября 2021 г.). «Алгоритм (2+\epsilon)-аппроксимации максимального независимого набора прямоугольников». arXiv : 2106.00623 [ cs.CG ].
^ Эрлебах, Т.; Янсен, К.; Зайдель, Э. (2005). «Схемы полиномиальной аппроксимации геометрических графов пересечений». SIAM Journal по вычислительной технике . 34 (6): 1302. дои : 10.1137/s0097539702402676 .
^ Фу, Б. (2011). «Теория и применение геометрических разделителей ограниченной ширины» . Журнал компьютерных и системных наук . 77 (2): 379–392. дои : 10.1016/j.jcss.2010.05.003 .
^ Jump up to: ^а ^б ^с Чан, ТМ ; Хар-Пелед, С. (2012). «Алгоритмы аппроксимации максимально независимого множества псевдодисков» . Дискретная и вычислительная геометрия . 48 (2): 373. arXiv : 1103.1431 . дои : 10.1007/s00454-012-9417-5 . S2CID 38183751 .
^ Jump up to: ^а ^б ^с Агарвал, ПК; Мустафа, Нью-Хэмпшир (2006). «Независимый набор графов пересечений выпуклых объектов в 2D». Вычислительная геометрия . 34 (2): 83. doi : 10.1016/j.comgeo.2005.12.001 .
^ Jump up to: ^а ^б Фокс, Дж.; Пах, Дж. Н. (2011). «Вычисление числа независимости графов пересечений». Материалы двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 1161. CiteSeerX 10.1.1.700.4445 . дои : 10.1137/1.9781611973082.87 . ISBN 978-0-89871-993-2 . S2CID 15850862 .

[1] Рави, СС; Хант, HB (1987). «Применение теоремы о плоском сепараторе к задачам подсчета». Письма об обработке информации . 25 (5): 317. дои : 10.1016/0020-0190(87)90206-7 . , Смит, В.Д.; Вормальд, Северная Каролина (1998). «Теоремы и приложения о геометрическом сепараторе» . Материалы 39-го ежегодного симпозиума по основам информатики (кат. № 98CB36280) . п. 232. дои : 10.1109/sfcs.1998.743449 . ISBN 978-0-8186-9172-0 . S2CID 17962961 .

[Agarwal1998-2] Jump up to: ^а ^б ^с ^д Агарвал, ПК; Ван Кревелд, М.; Сури, С. (1998). «Размещение этикетки по максимально независимому множеству в прямоугольниках». Вычислительная геометрия . 11 (3–4): 209. doi : 10.1016/s0925-7721(98)00028-5 . hdl : 1874/18908 .

[Marathe1995-3] Jump up to: ^а ^б Марат, МВ; Бреу, Х.; Хант, HB; Рави, СС; Розенкранц, диджей (1995). «Простые эвристики для единичных дисковых графов». Сети . 25 (2): 59. arXiv : math/9409226 . дои : 10.1002/net.3230250205 .

[HochbaumMaass1985-4] Jump up to: ^а ^б Хохбаум, Д.С. ; Маасс, В. (1985). «Аппроксимационные схемы для задач покрытия и упаковки в обработке изображений и СБИС» . Журнал АКМ . 32 : 130–136. дои : 10.1145/2455.214106 . S2CID 2383627 .

[Chan2003-5] Jump up to: ^а ^б ^с Чан, ТМ (2003). «Схемы аппроксимации полиномиального времени для упаковки и прокалывания толстых объектов». Журнал алгоритмов . 46 (2): 178–189. CiteSeerX 10.1.1.21.5344 . дои : 10.1016/s0196-6774(02)00294-8 .

[6] Чалермсук, П.; Чужой, Дж. (2009). «Максимально независимый набор прямоугольников». Материалы двадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 892. дои : 10.1137/1.9781611973068.97 . ISBN 978-0-89871-680-1 .

[7] Чалермсук, Паринья; Вальчак, Бартош (01 января 2021 г.), «Раскраска и набор прямоугольников, не зависящий от максимального веса», Труды симпозиума ACM-SIAM 2021 года по дискретным алгоритмам (SODA) , Труды Общества промышленной и прикладной математики, стр. 860– 868, arXiv : 2007.07880 , doi : 10.1137/1.9781611976465.54 , ISBN 978-1-61197-646-5 , S2CID 220525811

[8] Абед, Фидаа; Чалермсук, Паринья; Корреа, Хосе; Карренбауэр, Андреас; Перес-Лантеро, Пабло; Сото, Хосе А.; Визе, Андреас (2015). О последовательности гильотинной резки . стр. 1–19. doi : 10.4230/LIPIcs.APPROX-RANDOM.2015.1 . ISBN 978-3-939897-89-7 .

[9] Митчелл, Джозеф С.Б. (25 июня 2021 г.). «Аппроксимация максимального независимого множества для прямоугольников на плоскости». arXiv : 2101.00326 [ cs.CG ].

[10] Гальвес, Уолдо; Хан, Ариндам; Мари, Матье; Мёмке, Тобиас; Питту, Мадхусудхан Редди; Визе, Андреас (01 января 2022 г.), «Алгоритм с тремя приближениями для максимального независимого набора прямоугольников» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2022 г. , Труды Общества промышленной и прикладной математики, стр. 894–905, doi : 10.1137/1.9781611977073.38 , ISBN. 978-1-61197-707-3 , S2CID 235265867 , получено 29 сентября 2022 г.

[11] Гальвез, Уолдо; Хан, Ариндам; Муж Мэтью; Мёмке, Тобиас; Редди, Мадхусудхан; Визе, Андреас (26 сентября 2021 г.). «Алгоритм (2+\epsilon)-аппроксимации максимального независимого набора прямоугольников». arXiv : 2106.00623 [ cs.CG ].

[Erlebach2005-12] Эрлебах, Т.; Янсен, К.; Зайдель, Э. (2005). «Схемы полиномиальной аппроксимации геометрических графов пересечений». SIAM Journal по вычислительной технике . 34 (6): 1302. дои : 10.1137/s0097539702402676 .

[Fu-13] Фу, Б. (2011). «Теория и применение геометрических разделителей ограниченной ширины» . Журнал компьютерных и системных наук . 77 (2): 379–392. дои : 10.1016/j.jcss.2010.05.003 .

[ChanHarPeled2012-14] Jump up to: ^а ^б ^с Чан, ТМ ; Хар-Пелед, С. (2012). «Алгоритмы аппроксимации максимально независимого множества псевдодисков» . Дискретная и вычислительная геометрия . 48 (2): 373. arXiv : 1103.1431 . дои : 10.1007/s00454-012-9417-5 . S2CID 38183751 .

[am06-15] Jump up to: ^а ^б ^с Агарвал, ПК; Мустафа, Нью-Хэмпшир (2006). «Независимый набор графов пересечений выпуклых объектов в 2D». Вычислительная геометрия . 34 (2): 83. doi : 10.1016/j.comgeo.2005.12.001 .

[fp11-16] Jump up to: ^а ^б Фокс, Дж.; Пах, Дж. Н. (2011). «Вычисление числа независимости графов пересечений». Материалы двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 1161. CiteSeerX 10.1.1.700.4445 . дои : 10.1137/1.9781611973082.87 . ISBN 978-0-89871-993-2 . S2CID 15850862 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]