Проблема типа LP

При изучении алгоритмов ( проблема типа LP также называемая обобщенной линейной программой ) представляет собой задачу оптимизации , которая имеет определенные свойства, присущие низкоразмерным линейным программам , и может быть решена с помощью аналогичных алгоритмов. Задачи типа LP включают в себя множество важных задач оптимизации, которые сами по себе не являются линейными программами, например, задачу поиска наименьшего круга , содержащего заданный набор плоских точек. Их можно решить с помощью комбинации рандомизированных алгоритмов за время, линейное по количеству элементов, определяющих проблему, и субэкспоненциальное по размерности проблемы.

Определение

Проблемы типа LP были определены Шариром и Вельцлом (1992) как проблемы, в которых в качестве входных данных дается конечное множество $S$ элементов и функция $f$ , которая отображает подмножества $S$ в значения из полностью упорядоченного набора. Функция должна удовлетворять двум ключевым свойствам:

Монотонность: для каждых двух множеств $A \subseteq B \subseteq S$ , f ( A ) ⩽ f ( B ) ⩽ f ( S ).
Локальность: для каждых двух множеств $A \subseteq B \subseteq S$ и каждого элемента $x$ в $S$ , если $f (A) = f (B) = f (A \cup {x})$ , то $f (A) = f (B \cup {x})$ .

Базисом имеет задачи типа LP является множество $B \subseteq S,$ обладающее тем свойством, что каждое собственное подмножество $B$ меньшее значение $f,$ чем $само B$ , а размерность (или комбинаторная размерность ) задачи типа LP определяется как — максимальная мощность базиса.

Предполагается, что алгоритм оптимизации может оценивать функцию $f$ только на множествах, которые сами являются базисами или образуются путем добавления одного элемента к базису. Альтернативно, алгоритм может быть ограничен двумя примитивными операциями: проверкой нарушения , которая определяет для базиса $B$ и элемента $x$ , является ли $f (B) = f (B \cup {x})$ , и вычислением базиса , которое (с тем же самым входы) находит базис $B \cup {x$ }. Задача алгоритма состоит в том, чтобы оценить $f (S),$ используя только эти ограниченные оценки или примитивы.

Примеры и приложения

LP шары

Линейная программа может быть определена системой $d$ неотрицательных действительных переменных с учетом $n$ линейных ограничений-неравенств вместе с неотрицательной линейной целевой функцией, которую необходимо минимизировать. Это можно поместить в структуру задач типа LP, если $S$ будет набором ограничений и определить $f (A)$ (для подмножества $A$ ограничений) как минимальное значение целевой функции меньшей линейной программы, определяемой формулой $А.$ При подходящих предположениях общего положения (во избежание того, чтобы несколько точек решения имели одно и то же оптимальное значение целевой функции) это удовлетворяет требованиям монотонности и локальности задачи LP-типа и имеет комбинаторную размерность, равную числу $d$ переменных. ^[1] Аналогично, целочисленная программа (состоящая из набора линейных ограничений и линейной целевой функции, как в линейной программе, но с дополнительным ограничением, согласно которому переменные должны принимать только целочисленные значения) удовлетворяет как свойствам монотонности, так и локальности ЛП. Задача -типа с теми же общими предположениями, что и для линейных программ. Теоремы Белла (1977) и Скарфа (1977) показывают, что для целочисленной программы с $d$ переменными комбинаторная размерность не превышает $2 д$ . ^[1]

Многие естественные задачи оптимизации в вычислительной геометрии относятся к типу ЛП:

Задача о наименьшем круге — это задача нахождения минимального радиуса круга, содержащего заданный набор из $n$ точек на плоскости. Он удовлетворяет монотонности (добавление дополнительных точек может только увеличить круг) и локальности (если наименьший круг для множества $A$ содержит $B$ и $x$ , то тот же круг также содержит $B \cup {x$ }). Поскольку наименьший круг всегда определяется тремя точками, задача наименьшего круга имеет комбинаторную размерность три, хотя она определяется с использованием двумерной евклидовой геометрии. ^[2] В более общем смысле, наименьший охватывающий шар точек в $измерениях d$ образует задачу типа LP комбинаторной размерности $d + 1$ . Задачу о наименьшем круге можно обобщить на случай наименьшего шара, заключающего в себе набор шаров: ^[3] до наименьшего шара, который касается или окружает каждый из набора шаров, ^[4] к взвешенной задаче 1 центра , ^[5] или к аналогичным проблемам с вмещающим шаром меньшего размера в неевклидовых пространствах, таких как пространство с расстояниями, определяемыми дивергенцией Брегмана . ^[6] Связанная с этим проблема поиска наименьшего охватывающего эллипсоида также является проблемой типа LP, но с большей комбинаторной размерностью $d (d + 3)/2$ . ^[7]
Пусть $K 0, K 1, ...$ — последовательность из $n$ выпуклых множеств в $d$ -мерном евклидовом пространстве и предположим, что мы хотим найти самый длинный префикс этой последовательности, имеющий общую точку пересечения. Это можно выразить как задачу типа ЛП, в которой $f (A) = - i$ , где K _i — первый член A , не принадлежащий пересекающемуся префиксу A , и где $f (A) = - n,$ если существует нет такого члена. Комбинаторная размерность этой системы равна $d + 1$ . ^[8]
Предположим, нам дан набор прямоугольных блоков, выровненных по осям, в трехмерном пространстве, и мы хотим найти линию, направленную в положительный октант пространства, которая пересекает все блоки. Это можно выразить как задачу типа ЛП с комбинаторной размерностью 4. ^[9]
Задачу нахождения ближайшего расстояния между двумя выпуклыми многогранниками , заданными их наборами вершин, можно представить как задачу LP-типа. В этой формулировке набор $S$ представляет собой набор всех вершин в обоих многогранниках, а значение функции $f (A)$ представляет собой отрицание наименьшего расстояния между выпуклыми оболочками двух подмножеств $A$ вершин в двух многогранниках. Комбинаторная размерность задачи равна $d + 1$ , если два многогранника не пересекаются, или $d + 2,$ если они имеют непустое пересечение. ^[1]
Пусть $S = {f 0, f 1, ...$ } — набор квазивыпуклых функций . Тогда поточечный максимум $max i fi сам по себе является квазивыпуклым, и$ задача нахождения минимального значения $max i fi является$ задачей типа LP. Он имеет комбинаторную размерность не более $2 d + 1$ , где $d$ — размерность области определения функций, но для достаточно гладких функций комбинаторная размерность меньше, не более $d + 1$ . Многие другие задачи типа ЛП также можно выразить с помощью квазивыпуклых функций; например, проблема наименьшего охватывающего круга — это задача минимизации $max i fi,$ где каждая из функций $fi измеряет$ евклидово расстояние от одной из заданных точек. ^[10]

Задачи типа LP также использовались для определения оптимальных результатов некоторых игр в алгоритмической теории игр . ^[11] улучшить размещение вершин в сетках метода конечных элементов , ^[12] решить проблемы с размещением объектов , ^[13] анализировать временную сложность некоторых алгоритмов поиска с экспоненциальным временем, ^[14] и восстанавливать трехмерное положение объектов по их двухмерным изображениям. ^[15]

Алгоритмы

Зайдель

Зейдель (1991) предложил алгоритм маломерного линейного программирования, который можно адаптировать к структуре задач типа LP. Алгоритм Зейделя принимает на вход набор $S$ и отдельный набор $X$ (изначально пустой) элементов, о которых известно, что они принадлежат оптимальному базису. Затем он рассматривает оставшиеся элементы один за другим в случайном порядке, выполняя тесты на нарушение для каждого из них и, в зависимости от результата, выполняя рекурсивный вызов того же алгоритма с большим набором известных базисных элементов. Это можно выразить с помощью следующего псевдокода:

function seidel(S, f, X) is
    R := empty set
    B := X
    for x in a random permutation of S:
        if f(B) ≠ f(B ∪ {x}):
            B := seidel(R, f, X ∪ {x})
        R := R ∪ {x}
    return B

В задаче с комбинаторной размерностью $d$ проверка нарушения на $i$ -й итерации алгоритма не удалась только тогда, когда $x$ является одним из $d - | Х |$ оставшиеся базисные элементы, что происходит с вероятностью не более $(d - | X |)/ i$ . На основе этого расчета можно показать, что общее ожидаемое количество тестов на нарушения, выполняемых алгоритмом, равно $O(d! n)$ , линейное по $n$ , но хуже, чем экспоненциальное по $d$ .

Кларксон

Кларксон (1995) определяет два алгоритма, рекурсивный алгоритм и итерационный алгоритм, для линейного программирования, основанного на методах случайной выборки, и предлагает комбинацию этих двух алгоритмов, которая вызывает итерационный алгоритм из рекурсивного алгоритма. Рекурсивный алгоритм неоднократно выбирает случайные выборки, размер которых примерно равен квадратному корню из входного размера, рекурсивно решает проблему выборки, а затем использует тесты на нарушения, чтобы найти подмножество оставшихся элементов, которое должно включать хотя бы один базовый элемент:

function recursive(S, f) is
    X := empty set
    repeat
        R := a random subset of S with size d√n
        B := basis for R ∪ X, computed recursively
        V := {x | f(B) ≠ f(B ∪ {x})}
        X := X ∪ V
    until V is empty
    return B

На каждой итерации ожидаемый размер $V$ равен $O(\sqrt n)$ , ^[16] и всякий раз, когда $V$ непусто, он включает по крайней мере один новый элемент конечного базиса $S$ . Следовательно, алгоритм выполняет не более $d$ итераций, каждая из которых выполняет $n$ тестов на нарушение и делает один рекурсивный вызов подзадачи размером $O(d \sqrt n)$ .

Итерационный алгоритм Кларксона присваивает веса каждому элементу $S$ , первоначально все они равны. Затем он выбирает набор $R$ из $9 d 2$ элементы из $S$ случайным образом и вычисляет наборы $B$ и $V$ , как в предыдущем алгоритме. Если общий вес $V$ не более чем в $2/(9 d - 1)$ раз превышает общий вес $S$ (как это происходит с постоянной вероятностью), то алгоритм удваивает веса каждого элемента $V$ и, как и прежде, повторяет этот процесс до тех пор, пока $V$ становится пустым. Можно показать, что на каждой итерации вес оптимального базиса увеличивается с большей скоростью, чем общий вес $S$ , из чего следует, что алгоритм должен завершиться за $O(log n)$ итераций.

Используя рекурсивный алгоритм для решения заданной задачи, переключившись на итерационный алгоритм для его рекурсивных вызовов, а затем снова переключившись на алгоритм Зейделя для вызовов, сделанных итеративным алгоритмом, можно решить данную задачу типа LP, используя $O(дн + д! О(1) log n)$ тесты на нарушение.

Применительно к линейной программе этот алгоритм можно интерпретировать как двойной симплексный метод . ^[17] С помощью некоторых дополнительных вычислительных примитивов, помимо проверки на нарушение и примитивов базисных вычислений, этот метод можно сделать детерминированным. ^[18]

Матушек, Шарир и Вельцль

Матушек, Шарир и Вельцль (1996) описывают алгоритм, который использует дополнительное свойство линейных программ, которое не всегда сохраняется в других задачах типа LP, а именно: все базы имеют одинаковую мощность друг друга. Если задача типа LP не обладает этим свойством, ее можно добиться, добавив $d$ новых фиктивных элементов и изменив функцию $f$ так, чтобы она возвращала упорядоченную пару ее старого значения $f (A)$ и числа $min(d,| A |)$ , упорядоченный лексикографически .

Вместо того, чтобы добавлять элементы S по одному или находить образцы элементов, Матушек, Шарир и Вельцль (1996) описывают алгоритм, который удаляет элементы по одному. На каждом этапе он поддерживает базис $C$ , который первоначально может быть набором фиктивных элементов. Его можно описать следующим псевдокодом:

function msw(S, f, C) is
    if S = C then
        return C
    choose a random element x of S \ C
    B = msw(S \ x, f, C)
    if f(B) ≠ f(B ∪ {x}) then
        B := basis(B ∪ {x})
        B := msw(S, f, B)
    return B

В большинстве рекурсивных вызовов алгоритма проверка на нарушение завершается успешно, а оператор if пропускается. Однако с небольшой вероятностью тест на нарушение не пройден, и алгоритм выполняет дополнительные базисные вычисления, а затем дополнительный рекурсивный вызов. Как показывают авторы, ожидаемое время алгоритма линейно по n и экспоненциально по квадратному корню из $d log n$ . Комбинируя этот метод с рекурсивными и итеративными процедурами Кларксона, эти две формы зависимости от времени можно отделить друг от друга, в результате чего получается алгоритм, выполняющий тесты на нарушение O( dn ) во внешнем рекурсивном алгоритме и экспоненциальное число во внешнем рекурсивном алгоритме. квадратный корень из $d log d$ на нижних уровнях алгоритма. ^[19]

Вариации

Оптимизация с выбросами

Матушек (1995) рассматривает вариант задач оптимизации типа LP, в которых вместе с набором $S$ и целевой функцией $f$ задано число $k$ ; задача состоит в том, чтобы удалить $k$ элементов из $S$ , чтобы сделать целевую функцию на оставшемся множестве как можно меньшей. Например, применительно к задаче о наименьшем круге это даст наименьший круг, содержащий все $кроме k$ заданные плоские точки, . Он показывает, что для всех невырожденных задач типа ЛП (т. е. задач, в которых все базисы имеют различные значения) эта задача может быть решена за время $O(nk д)$ , решив набор $O(k д)$ Проблемы типа LP, определяемые подмножествами $S$ .

Неявные проблемы

Некоторые задачи геометрической оптимизации могут быть выражены как задачи типа LP, в которых количество элементов в формулировке типа LP значительно больше, чем количество значений входных данных для задачи оптимизации. В качестве примера рассмотрим набор из $n$ точек плоскости, каждая из которых движется с постоянной скоростью. В любой момент времени диаметр этой системы равен максимальному расстоянию между двумя ее точками. Задачу нахождения момента времени, в который диаметр минимизируется, можно сформулировать как минимизацию поточечного максимума $O(n 2)$ квазивыпуклые функции, по одной на каждую пару точек, измеряющие евклидово расстояние между парой как функцию времени. Таким образом, ее можно решить как задачу типа ЛП комбинаторной размерности два на множестве $O(n 2)$ элементов, но этот набор существенно больше количества входных точек. ^[20]

Чан (2004) описывает алгоритм решения неявно определенных задач типа LP, таких как эта, в которой каждый элемент типа LP определяется $k$ -кортежом входных значений для некоторой константы $k$ . Чтобы применить его подход, должен существовать алгоритм решения , который может определить для данного базиса $B$ типа LP и набора $S$ из $n$ входных значений, является ли $B$ базисом для проблемы типа LP, определяемой $S$ .

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

Если количество входных значений ниже некоторого порогового значения, найдите набор элементов типа LP, который он определяет, и решите полученную явную задачу типа LP.
В противном случае разделите входные значения на подходящее число, большее, чем $k$ подмножеств одинакового размера $S i$ .
Если $f$ является целевой функцией для неявно определенной проблемы типа LP, которую необходимо решить, затем определите функцию $g$ , которая отображает коллекции подмножеств $Si в$ значение $f$ в объединении коллекции. Тогда совокупность подмножеств $Si .$ и целевая функция $g$ сами по себе определяют задачу LP-типа той же размерности, что и неявная задача, которую необходимо решить
Решите (явную) задачу типа LP, определенную $g,$ с помощью алгоритма Кларксона, который выполняет линейное количество тестов на нарушение и полилогарифмическое количество базовых оценок. Базисные оценки для $g$ могут выполняться посредством рекурсивных вызовов алгоритма Чана, а проверки нарушений могут выполняться посредством вызовов алгоритма принятия решения.

Предполагая, что алгоритм принятия решения занимает некоторое время $O(T (n) )$ , которое растет по крайней мере полиномиально в зависимости от размера входных данных $n$ , Чен показывает, что порог для переключения на явную формулировку LP и количество подмножеств в разбиении можно выбрать таким образом, чтобы неявный алгоритм оптимизации типа LP также выполнялся за время $O(T (n))$ .

Например, для минимального диаметра движущихся точек алгоритму решения необходимо только вычислить диаметр набора точек в фиксированное время - проблема, которую можно решить за $время O(n log n),$ используя метод вращающихся штангенциркулей . Следовательно, алгоритм Чана для нахождения времени минимизации диаметра также требует времени $O(n log n)$ . Чан использует этот метод, чтобы найти точку максимальной глубины Тьюки среди заданного набора из $n$ точек в $d$ -мерном евклидовом пространстве за время $O(n д - 1 + п журнал п)$ . Похожий метод использовался Брассом, Генрихом-Литаном и Морином (2003), чтобы найти точку максимальной глубины Тьюки для равномерного распределения на выпуклом многоугольнике.

История и связанные с ней проблемы

Открытие алгоритмов линейного времени для линейного программирования и наблюдение того, что одни и те же алгоритмы во многих случаях могут использоваться для решения задач геометрической оптимизации, которые не являются линейными программами, восходят, по крайней мере, к Мегиддо ( 1983 , 1984 ), который дал линейное ожидаемое время. алгоритм как для линейных программ с тремя переменными, так и для задачи наименьшего круга. Однако Мегиддо сформулировал обобщение линейного программирования геометрически, а не комбинаторно, как задачу выпуклой оптимизации , а не как абстрактную задачу о системах множеств. Точно так же Дайер (1986) и Кларксон (в версии Clarkson 1995 , представленной на конференции 1988 года ) заметили, что их методы можно применять как к выпуклым программам, так и к линейным программам. Дайер (1992) показал, что задачу минимального охватывающего эллипсоида можно также сформулировать как задачу выпуклой оптимизации, добавив небольшое количество нелинейных ограничений. Использование рандомизации для улучшения временных ограничений для низкоразмерного линейного программирования и связанных с ним задач было впервые использовано Кларксоном и Дайер и Фриз (1989) .

Определение задач LP-типа в терминах функций, удовлетворяющих аксиомам локальности и монотонности, взято из Шарира и Вельцла (1992) , но другие авторы в тот же период времени сформулировали альтернативные комбинаторные обобщения линейных программ. Например, в системе, разработанной (1995) , функция $f$ заменяется полным упорядочением на подмножествах $S.$ Гертнером В задаче типа ЛП можно разорвать связи и создать тотальный порядок, но только за счет увеличения комбинаторной размерности. ^[21] Кроме того, как и в задачах типа LP, Гертнер определяет определенные примитивы для выполнения вычислений над подмножествами элементов; однако его формализация не имеет аналога комбинаторного измерения.

Другое абстрактное обобщение как линейных программ, так и задач линейной дополнительности , сформулированное Стикни и Уотсоном (1978) и позднее изученное несколькими другими авторами, касается ориентации ребер гиперкуба , при которой каждая грань гиперкуба (включая весь гиперкуб) как грань) имеет уникальный сток — вершину, не имеющую исходящих ребер. Ориентацию этого типа можно сформировать из задачи типа LP, сопоставляя подмножества S вершинам гиперкуба таким образом, чтобы два подмножества отличались одним элементом тогда и только тогда, когда соответствующие вершины смежны, и ориентируя ребро между соседними множествами $A \subseteq B$ в сторону $B,$ если $f (A) \neq f (B),$ и в сторону $A$ в противном случае. Полученная ориентация обладает дополнительным свойством, заключающимся в том, что она образует ориентированный ациклический граф , из которого можно показать, что рандомизированный алгоритм может найти уникальный сток всего гиперкуба (оптимальный базис задачи типа LP) за несколько шагов. экспонента от квадратного корня из $н$ . ^[22]

Недавно разработанная структура пространств нарушителей обобщает проблемы типа LP в том смысле, что каждая проблема типа LP может быть смоделирована пространством нарушителей, но не обязательно наоборот. Пространства нарушителей определяются аналогично задачам типа LP с помощью функции $f,$ которая отображает множества в значения целевой функции, но значения $f$ не упорядочены. Несмотря на отсутствие порядка, каждое множество $S$ имеет четко определенный набор базисов (минимальные наборы с тем же значением, что и все множество), которые можно найти с помощью вариаций алгоритмов Кларксона для задач типа LP. Действительно, было показано, что пространства нарушителей точно характеризуют системы, которые можно решить с помощью алгоритмов Кларксона. ^[23]

Примечания

^ Jump up to: Перейти обратно: ^а ^б ^с Матоусек, Шарир и Вельцль (1996) .
^ Хотя проблема наименьшего круга была впервые заявлена как проблема типа LP Матушеком, Шариром и Вельцлем (1996) , в нескольких более ранних статьях описывались алгоритмы для этой проблемы, основанные на идеях низкомерного линейного программирования, включая Мегиддо (1983) и Вельцль (1991) .
^ Фишер и Гертнер (2004) .
^ Леффлер и ван Кревелд (2010) .
^ Дайер (1986) .
^ Нильсен и Нок (2008) .
^ Матоусек, Шарир и Вельцль (1996) ; Вельцль (1991) .
^ Чан (2004) .
^ Амента (1994) .
^ Амента, Берн и Эппштейн (1999) ; Эпштейн (2005) .
^ Халман (2007) .
^ Амента, Берн и Эппштейн (1999) .
^ Порт, Родригес-Чиа и Тамир (2010) .
^ Эппштейн (2006) .
^ Это (2007) .
^ хвостовые границы размера $V$ Также известны : см. Gärtner & Welzl (2001) .
^ Резьба (1992) .
^ Шазель и Матушек (1996) .
^ Матушек, Шарир и Вельцль (1996) . Очень похожая временная граница для линейного программирования была дана Калаем (1992) .
^ Формулировка этой проблемы типа LP была дана Чаном (2004) , но ранее она изучалась с использованием других алгоритмических методов Гуптой, Джанарданом и Смидом (1996) . Чен также цитирует неопубликованную рукопись Кларксона, посвященную $алгоритму времени O(n log n)$ , соответствующему времени, которое может быть достигнуто с помощью неявного подхода типа LP.
^ Матоусек (2009) .
^ Сабо и Вельцль (2001) .
^ Гертнер и др. (2008) ; Бриз и Гертнер (2011) .

Ссылки

Амента, Нина (1994), «Теоремы типа Хелли и обобщенное линейное программирование» (PDF) , Дискретная и вычислительная геометрия , 12 (3): 241–261, doi : 10.1007/BF02574379 , MR 1298910 , S2CID 26667725 .
Амента, Нина ; Берн, Маршалл; Эппштейн, Дэвид (1999), «Оптимальное размещение точек для сглаживания сетки», Journal of Algorithms , 30 (2): 302–322, arXiv : cs.CG/9809081 , doi : 10.1006/jagm.1998.0984 , MR 1671836 , S2CID 182728 .
Белл, Дэвид Э. (1977), «Теорема о целочисленной решетке» (PDF) , Исследования по прикладной математике , 56 (2): 187–188, doi : 10.1002/sapm1977562187 , MR 0462617 .
Брасс, Питер; Генрих-Литан, Лаура; Морин, Пэт (2003), «Вычисление центра площади выпуклого многоугольника» (PDF) , Международный журнал вычислительной геометрии и приложений , 13 (5): 439–445, doi : 10.1142/S021819590300127X , MR 2012837 .
Бриз, Ив; Гертнер, Бернд (2011), «Алгоритм Кларксона для пространств-нарушителей» (PDF) , Вычислительная геометрия: теория и приложения , 44 (2): 70–81, arXiv : 0906.4706 , doi : 10.1016/j.comgeo.2010.09.003 , МР 2737285 , S2CID 1233875 .
Чан, Тимоти М. (2004), «Оптимальный рандомизированный алгоритм для максимальной глубины Тьюки» (PDF) , Proc. 15-й симпозиум ACM-SIAM. Дискретные алгоритмы , стр. 423–429 .
Шазель, Бернар ; Матушек, Иржи (1996), «О детерминированных алгоритмах линейного времени для задач оптимизации в фиксированной размерности» (PDF) , Journal of Algorithms , 21 (3): 579–597, doi : 10.1006/jagm.1996.0060 , MR 1417665 , S2CID 2482481 .
Кларксон, Кеннет Л. (1995), «Алгоритмы Лас-Вегаса для линейного и целочисленного программирования при малых размерностях» (PDF) , Journal of the ACM , 42 (2): 488–499, doi : 10.1145/201019.201036 , MR 1409744 , S2CID 6953625 .
Дайер, Мартин Э. (1986), «О технике многомерного поиска и ее применении к евклидовой проблеме одного центра», SIAM Journal on Computing , 15 (3): 725–738, doi : 10.1137/0215052 , MR 0850419 .
Дайер, Мартин Э. (1992), «Класс выпуклых программ с приложениями к вычислительной геометрии», Proc. 8-й симпозиум по вычислительной геометрии (SCG '92) , Берлин, Германия, стр. 9–15, doi : 10.1145/142675.142681 , ISBN 0-89791-517-8 , S2CID 7654513 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .
Дайер, Мартин Э.; Фриз, Алан М. (1989), «Рандомизированный алгоритм для линейного программирования фиксированной размерности», Mathematical Programming , (Ser. A), 44 (2): 203–212, doi : 10.1007/BF01587088 , MR 1003560 , S2CID 206800147 .
Эппштейн, Дэвид (2005), «Квазивыпуклое программирование», Гудман, Джейкоб Э.; Пах, Янош ; Вельцль, Эмо (ред.), Комбинаторная и вычислительная геометрия , публикации MSRI, том. 52, Кембриджский университет. Press, стр. 287–331, arXiv : cs.CG/0412046 , MR 2178325 .
Эппштейн, Дэвид (2006), «Квазивыпуклый анализ многомерных рекуррентных уравнений для алгоритмов обратного отслеживания», ACM Transactions on Algorithms , 2 (4): 492–509, arXiv : cs.DS/0304018 , doi : 10.1145/1198513.1198515 , MR 2284242 , S2CID 9980061 .
Фишер, Каспар; Гертнер, Бернд (2004), «Наименьший вмещающий шар из шаров: комбинаторная структура и алгоритмы» (PDF) , Международный журнал вычислительной геометрии и приложений , 14 (4–5): 341–378, doi : 10.1142/S0218195904001500 , MR 2087827 .
Гертнер, Бернд (1995), «Субэкспоненциальный алгоритм для абстрактных задач оптимизации» (PDF) , SIAM Journal on Computing , 24 (5): 1018–1035, doi : 10.1137/S0097539793250287 , MR 1350756 .
Гертнер, Бернд; Матушек, Иржи ; Рюст, Л.; Шковрон П. (2008), «Пространства нарушителей: структура и алгоритмы», Discrete Applied Mathematics , 156 (11): 2124–2141, arXiv : cs.DM/0606087 , doi : 10.1016/j.dam.2007.08.048 , МР 2437006 .
Гертнер, Бернд; Вельцль, Эмо (2001), «Простая лемма выборки: анализ и приложения в геометрической оптимизации» (PDF) , Дискретная и вычислительная геометрия , 25 (4): 569–590, doi : 10.1007/s00454-001-0006-2 , МР 1838420 , S2CID 14263014 .
Гупта, Просенджит; Джанардан, Рави; Смид, Михил (1996), «Быстрые алгоритмы для решения проблем столкновений и близости с движущимися геометрическими объектами», Вычислительная геометрия. Теория и приложения , 6 (6): 371–391, doi : 10.1016/0925-7721(95)00028-3 , hdl : 11858/00-001M-0000-0014-B50E-D , MR 1415267 .
Халман, Нир (2007), «Простые стохастические игры, игры на четность, игры со средним выигрышем и игры со сниженным выигрышем — все это проблемы типа LP» , Algorithmica , 49 (1): 37–50, doi : 10.1007/s00453-007-0175 -3 , МР 2344393 , S2CID 8183965 .
Калаи, Гил (1992), «Субэкспоненциальный рандомизированный симплекс-алгоритм», Proc. 24-й симпозиум ACM по теории вычислений , стр. 475–482, doi : 10.1145/129712.129759 , S2CID 17447465 .
Ли, Гонконг (2007), «Практический алгоритм $триангуляции L \infty$ с выбросами», Proc. Конференция IEEE. по компьютерному зрению и распознаванию образов (CVPR '07) , стр. 1–8, doi : 10.1109/CVPR.2007.383068 , hdl : 1885/39190 , ISBN 978-1-4244-1179-5 , S2CID 14882916 .
Леффлер, Мартен; ван Кревелд, Марк (2010), «Самая большая ограничивающая рамка, наименьший диаметр и связанные с этим проблемы с неточными точками» (PDF) , Теория и приложения вычислительной геометрии , 43 (4): 419–433, doi : 10.1016/j.comgeo. 2009.03.007 , МР 2575803 .
Матушек, Иржи (1995), «О геометрической оптимизации с небольшим количеством нарушаемых ограничений», Дискретная и вычислительная геометрия , 14 (4): 365–384, doi : 10.1007/BF02570713 , MR 1360943 .
Матушек, Иржи (2009), «Возврат к устранению вырождения в задачах типа ЛП», Дискретная и вычислительная геометрия , 42 (4): 517–526, doi : 10.1007/s00454-008-9085-7 , hdl : 20.500.11850/ 156948 , МР 2556452 .
Матушек, Иржи ; Шарир, Миша ; Вельцль, Эмо (1996), «Субэкспоненциальная граница для линейного программирования» (PDF) , Algorithmica , 16 (4–5): 498–516, doi : 10.1007/BF01940877 , S2CID 877032 .
Мегиддо, Нимрод (1983), «Алгоритмы линейного времени для линейного программирования в $R 3$ и связанные с ним проблемы», SIAM Journal on Computing , 12 (4): 759–776, doi : 10.1137/0212052 , MR 0721011 , S2CID 14467740 .
Мегиддо, Нимрод (1984), «Линейное программирование в линейное время при фиксированном измерении», Journal of the ACM , 31 (1): 114–127, doi : 10.1145/2422.322418 , MR 0821388 , S2CID 12686747 .
Нильсен, Франк; Нок, Ричард (2008), «На самом маленьком вмещающем информационном диске» (PDF) , Information Processing Letters , 105 (3): 93–97, doi : 10.1016/j.ipl.2007.08.007 , MR 2378119 , S2CID 7570507 .
Пуэрто, Дж.; Родригес-Чиа, AM; Тамир, А. (2010), «О плоской кусочно-квадратичной задаче с 1 центром», Algorithmica , 57 (2): 252–283, doi : 10.1007/s00453-008-9210-2 , MR 2587554 , S2CID 18587944 .
Скарф, Герберт Э. (1977), «Наблюдение за структурой неделимых производственных наборов», Труды Национальной академии наук Соединенных Штатов Америки , 74 (9): 3637–3641, Bibcode : 1977PNAS.. .74.3637S , doi : 10.1073/pnas.74.9.3637 , MR 0452678 , PMC 431672 , PMID 16592435 .
Зайдель, Раймунд (1991), «Маломерное линейное программирование и выпуклые оболочки стало проще», Дискретная и вычислительная геометрия , 6 (5): 423–434, doi : 10.1007/BF02574699 , MR 1115100 .
Шарир, Миша ; Велцль, Эмо (1992), «Комбинаторная оценка для линейного программирования и связанных с ним задач», Stacs 92 , Конспекты лекций по информатике, том. 577, Springer-Verlag, стр. 567–579, номер документа : 10.1007/3-540-55210-3_213 , ISBN. 978-3-540-55210-9 .
Стикни, Алан; Уотсон, Лэйн (1978), «Орграфовые модели алгоритмов типа Барда для задачи линейной дополнительности», Mathematics of Operations Research , 3 (4): 322–333, doi : 10.1287/moor.3.4.322 , MR 0509668 .
Сабо, Тибор; Вельцль, Эмо (2001), «Уникальные ориентации кубов» (PDF) , 42-й симпозиум IEEE по основам информатики (Лас-Вегас, Невада, 2001) , стр. 547–555, doi : 10.1109/SFCS.2001.959931 , ISBN 0-7695-1390-5 , MR 1948744 , S2CID 6597643 .
Вельцль, Эмо (1991), «Наименьшие вмещающие диски (шары и эллипсоиды)», в Маурере, Х. (ред.), Новые результаты и новые тенденции в информатике (PDF) , Конспекты лекций по информатике, том. 555 (изд. 555), Springer-Verlag, стр. 359–370, doi : 10.1007/BFb0038202 , ISBN 3-540-54869-6 .

[msw96-1] Jump up to: Перейти обратно: ^а ^б ^с Матоусек, Шарир и Вельцль (1996) .

[2] Хотя проблема наименьшего круга была впервые заявлена как проблема типа LP Матушеком, Шариром и Вельцлем (1996) , в нескольких более ранних статьях описывались алгоритмы для этой проблемы, основанные на идеях низкомерного линейного программирования, включая Мегиддо (1983) и Вельцль (1991) .

[3] Фишер и Гертнер (2004) .

[4] Леффлер и ван Кревелд (2010) .

[5] Дайер (1986) .

[6] Нильсен и Нок (2008) .

[7] Матоусек, Шарир и Вельцль (1996) ; Вельцль (1991) .

[8] Чан (2004) .

[9] Амента (1994) .

[10] Амента, Берн и Эппштейн (1999) ; Эпштейн (2005) .

[11] Халман (2007) .

[12] Амента, Берн и Эппштейн (1999) .

[13] Порт, Родригес-Чиа и Тамир (2010) .

[14] Эппштейн (2006) .

[15] Это (2007) .

[16] хвостовые границы размера $V$ Также известны : см. Gärtner & Welzl (2001) .

[17] Резьба (1992) .

[18] Шазель и Матушек (1996) .

[19] Матушек, Шарир и Вельцль (1996) . Очень похожая временная граница для линейного программирования была дана Калаем (1992) .

[20] Формулировка этой проблемы типа LP была дана Чаном (2004) , но ранее она изучалась с использованием других алгоритмических методов Гуптой, Джанарданом и Смидом (1996) . Чен также цитирует неопубликованную рукопись Кларксона, посвященную $алгоритму времени O(n log n)$ , соответствующему времени, которое может быть достигнуто с помощью неявного подхода типа LP.

[21] Матоусек (2009) .

[22] Сабо и Вельцль (2001) .

[23] Гертнер и др. (2008) ; Бриз и Гертнер (2011) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]