Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение [ править ]

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

  • Монотонность: для любых двух множеств A ⊆ B ⊆ S , f ( A ) ≤ f ( B ) ≤ f ( S ).
  • Локальность: для любых двух множеств A ⊆ B ⊆ S и каждого элемента x в S , если f ( A ) = f ( B ) = f ( A ∪ { x }) , то f ( A ) = f ( B ∪ { x }) .

Основа из задачи ЛП-типа представляет собой набор B ⊆ S со свойством , что каждое собственное подмножество B имеет меньшее значение F , чем B самого, и измерение (или комбинаторной размерности ) одной задачи ЛП-типа определяется - максимальная мощность базы.

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

Примеры и приложения [ править ]

Lp шары

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

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

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

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

Алгоритмы [ править ]

Зайдель [ править ]

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

функция seidel ( S , f , X ) - это  R  : = пустое множество B  : = X  для  x в случайной перестановке S : если  f ( B ) ≠ f ( B ∪ { x }): B  : = seidel ( R , f , базис ( X ∪ { x })) R  : = R ∪ { x } return  B

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

Кларксон [ править ]

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

функция рекурсивная ( S , f ) - это  X  : = повтор пустого множества R  : = случайное подмножество S с размером d√n B  : = базис для R ∪ X , вычисляемый рекурсивно V  : = { x | f ( B ) ≠ f ( B ∪ { x })} X  : = X ∪ V,  пока  V не станет пустым, верните  B

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

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

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

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

Матушек, Шарир и Вельцль [ править ]

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

Вместо того, чтобы добавлять элементы S по одному или искать образцы элементов, Matoušek, Sharir & Welzl (1996) описывают алгоритм, который удаляет элементы по одному. На каждом этапе он поддерживает базис C, который изначально может быть набором фиктивных элементов. Это можно описать следующим псевдокодом:

функция msw ( S , f , C ) :  если  S = C,  то  вернуть  C выбрать случайный элемент x из S \ C  B = msw ( S \ x , f , C ), если  f ( B ) ≠ f (B ∪ {x }), то  B  : =  base ( 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, из данного набора плоских точек. Он показывает, что для всех невырожденных задач типа LP (то есть задач, в которых все базы имеют разные значения) эта проблема может быть решена за время O ( nk d ) путем решения набораO ( K d ) задачи ЛП-типа , определенные подмножества S .

Неявные проблемы [ править ]

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

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

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

  • Если количество входных значений ниже некоторого порогового значения, найдите набор элементов LP-типа, который он определяет, и решите полученную явную проблему LP-типа.
  • В противном случае разделите входные значения на подходящее количество, большее k подмножеств S i одинакового размера .
  • Если f - целевая функция для неявно определенной задачи LP-типа, которая должна быть решена, то определите функцию g, которая отображает коллекции подмножеств S i в значение f на объединении коллекции. Тогда набор подмножеств S i и сама целевая функция 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 d - 1 + nжурнал n ) . Аналогичный метод был использован Брассом, Генрихом-Литаном и Морином (2003), чтобы найти точку максимальной глубины Тьюки для равномерного распределения на выпуклом многоугольнике.

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

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

Определение задач типа LP в терминах функций, удовлетворяющих аксиомам локальности и монотонности, взято из Sharir & Welzl (1992) , но другие авторы в те же сроки сформулировали альтернативные комбинаторные обобщения линейных программ. Например, в рамках разработанной Гертнер (1995) , функция е заменяется общим порядком на подмножествах S . Разорвать связи в задаче типа LP можно для создания общего порядка, но только за счет увеличения комбинаторной размерности. [21]Кроме того, как и в задачах типа LP, Гертнер определяет некоторые примитивы для выполнения вычислений над подмножествами элементов; однако его формализация не имеет аналога комбинаторной размерности.

Другое абстрактное обобщение как линейных программ, так и задач линейной дополнительности , сформулированное Stickney & Watson (1978) и позднее изученное несколькими другими авторами, касается ориентации ребер гиперкуба со свойством, что каждая грань гиперкуба (включая весь гиперкуб) как грань) имеет единственный сток - вершину без выходящих ребер. Ориентация этого типа может быть сформирована из задачи типа LP путем сопоставления подмножеств S с вершинами гиперкуба таким образом, что два подмножества отличаются одним элементом тогда и только тогда, когда соответствующие вершины смежны, и ориентируя ребро между соседними множествами A ⊆ Bк B, если f ( A ) ≠ f ( B ), и к A в противном случае. Полученная ориентация имеет дополнительное свойство, состоящее в том, что она образует ориентированный ациклический граф , из которого можно показать, что рандомизированный алгоритм может найти уникальный сток всего гиперкуба (оптимальный базис задачи типа LP) за несколько шагов. экспонента в квадратном корне из  n . [22]

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

Заметки [ править ]

  1. ^ a b c Матушек, Шарир и Велцль (1996) .
  2. ^ Хотя задача наименьшего круга была впервые заявлена ​​как проблема LP-типа Матушеком, Шариром и Велзлом (1996) , в нескольких более ранних работах описывались алгоритмы для этой проблемы, основанные на идеях из низкоразмерного линейного программирования, в том числе Мегиддо (1983) и Вельцль (1991) .
  3. ^ Fischer & Гертнер (2004) .
  4. ^ Löffler и ван Kreveld (2010) .
  5. ^ Дайер (1986) .
  6. ^ Nielsen & Нок (2008) .
  7. ^ Matoušek, Шарир & Welzl (1996) ; Вельцль (1991) .
  8. ^ Чан (2004) .
  9. ^ Amenta (1994) .
  10. ^ Амента, Берн & Eppstein (1999) ; Эпштейн (2005) .
  11. ^ Halman (2007) .
  12. ^ Amenta, Bern & Эпштайна (1999) .
  13. ^ Пуэрто, Родригес-Чиа и Тамир (2010) .
  14. ^ Эпштайна (2006) .
  15. ^ Ли (2007) .
  16. ^ Хвостовые границы размера V также известны: см. Gärtner & Welzl (2001) .
  17. Перейти ↑ Kalai (1992) .
  18. ^ Chazelle & Matoušek (1996) .
  19. ^ Matoušek, Шарир & Welzl (1996) . Очень похожая временная граница для линейного программирования была также дана Калаи (1992) .
  20. ^ Формулировка этой проблемы типа LP была дана Чаном (2004) , но ранее она изучалась с использованием других алгоритмических методов Гуптой, Джанарданом и Смидом (1996) . Чан также цитирует неопубликованную рукопись Кларксона дляалгоритма времени O ( n log n ) , соответствующего времени, которое может быть достигнуто с помощью неявного подхода типа LP.
  21. ^ Matoušek (2009) .
  22. ^ Сабо & Welzl (2001) .
  23. ^ Gärtner et al. (2008) ; Бриз и Гертнер (2011) .

Ссылки [ править ]

  • Амента, Нина (1994), "Теорема типа Хелл и обобщенные линейное программирование" (PDF) , Дискретная и Вычислительная геометрия , 12 (3): 241-261, DOI : 10.1007 / BF02574379 , МР  1298910 , S2CID  26667725.
  • Амента, Нина ; Берн, Маршалл; Эппштейн, Дэвид (1999), «Оптимальное размещение точек для сглаживания сетки», Журнал алгоритмов , 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.
  • Брасс, Питер; Генрих-Литан, Лаура; Morin, патент (2003), "Вычисление центра области выпуклого многоугольника" (PDF) , Международный журнал вычислительной геометрии и приложений , 13 (5): 439-445, DOI : 10,1142 / S021819590300127X , МР  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..
  • Шазель, Бернар ; Matoušek Йиржи (1996), "О линейно-временных детерминированных алгоритмов для задач оптимизации в фиксированной размерности" (PDF) , журнал алгоритмов , 21 (3): 579-597, DOI : 10,1006 / jagm.1996.0060 , MR  1417665 , S2CID  2482481.
  • Кларксон, Кеннет Л. (1995), "Лас - Вегас алгоритмы для линейных и целочисленного программирования , когда размер мал" (PDF) , Журнал ACM , 42 (2): 488-499, DOI : 10,1145 / 201019,201036 , MR  1409744 , S2CID  6953625.
  • Дайер, Martin E. (1986), "О многомерном технике поиска и его применение к евклидовой задачи один-центр", SIAM журнал по вычислениям , 15 (3): 725-738, DOI : 10,1137 / 0215052 , MR  0850419.
  • Дайер, Мартин Э. (1992), "Класс выпуклых программ с приложениями к вычислительной геометрии", Proc. Восьмой симпозиум по вычислительной геометрии (SCG '92) ., Берлин, Германия, стр 9-15, DOI : 10,1145 / 142675,142681 , ISBN 0-89791-517-8, S2CID  7654513.
  • Дайер, Мартин Э .; Фриз, Алан М. (1989), "Рандомизированное алгоритм для фиксированного одномерного линейного программирования", Математическое программирование , (Ser A.), 44 (2): 203-212, DOI : 10.1007 / BF01587088 , МР  1003560 , S2CID  206800147.
  • Эпштейн, Дэвид (2005), «Квазивыпуклое программирование», в Goodman, Jacob E .; Пах, Янош ; Вельцль, Эмо (ред.), Комбинаторная и вычислительная геометрия , Публикации ИИГС, 52 , Cambridge Univ. 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 , М.Р.  2087827.
  • Гертнер, Бернд (1995), "субэкспоненциальный алгоритм для задач оптимизации абстрактной" (PDF) , SIAM журнал по вычислениям , 24 (5): 1018-1035, DOI : 10,1137 / S0097539793250287 , MR  1350756.
  • Гертнер, Бернд; Матушек, Иржи ; Rüst, L .; Шковрой П. (2008), «Пространства нарушителей: структура и алгоритмы», Дискретная прикладная математика , 156 (11): 2124–2141, arXiv : cs.DM/0606087 , doi : 10.1016 / j.dam.2007.08.048 , Руководство по ремонту  2437006.
  • Гертнер, Бернд; Welzl, Эмо (2001), "Простая выборка леммы: анализ и приложения в геометрической оптимизации" (PDF) , Дискретные и Вычислительная геометрия , 25 (4): 569-590, DOI : 10.1007 / s00454-001-0006-2 , Руководство по ремонту  1838420 , S2CID  14263014.
  • Гупта, Просенджит; Джанардан, Рави; Smid, Michiel (1996), "Быстрые алгоритмы решения проблем столкновения и близости с движущимися геометрическими объектами", Вычислительная геометрия. Теория и приложения , 6 (6): 371-391, DOI : 10,1016 / 0925-7721 (95) 00028-3 , ЛВП : 11858 / 00-001M-0000-0014-B50E-D , МР  1415267.
  • Halman, Nir (2007), «Простые стохастические игры, игры на четность, игры со средним выигрышем и игры со скидкой - все это проблемы типа LP» , Algorithmica , 49 (1): 37–50, doi : 10.1007 / s00453-007-0175 -3 , Руководство по ремонту  2344393 , S2CID  8183965.
  • Kalai, Gil (1992), "Субэкспоненциальный рандомизированный симплексный алгоритм", Proc. Двадцать четвёртая ACM симпозиум по теории вычислений ., Стр 475-482, DOI : 10,1145 / 129712,129759 , S2CID  17447465.
  • Ли, Хонгдун (2007), "Практический алгоритм триангуляции L ∞ с выбросами", Proc. IEEE Conf. по компьютерного зрения и распознавания образов (CVPR '07) , с 1-8,. DOI : 10,1109 / CVPR.2007.383068 , ЛВП : 1885/39190 , S2CID  14882916.
  • Лёффлер, Маартен; ван Kreveld, Марк (2010), "Самый большой ограничивающий прямоугольник, наименьший диаметр, и связанные с ними задачи по пунктам неточных" (PDF) , Вычислительная теория геометрии и приложений , 43 (4): 419-433, DOI : 10.1016 / j.comgeo. 2009.03.007 , MR  2575803.
  • Matoušek Йиржи (1995), "О геометрической оптимизации с несколькими нарушенных ограничениями", Дискретная и вычислительная геометрия , 14 (4): 365-384, DOI : 10.1007 / BF02570713 , MR  1360943.
  • Matoušek, Йиржи (2009), "Удаление вырождение в задачах ЛП-типа Revisited", Дискретные и Вычислительная геометрия , 42 (4): 517-526, DOI : 10.1007 / s00454-008-9085-7 , МР  2556452.
  • Матушек, Иржи ; Шарир, Миха ; Welzl, Эмо (1996), "субэкспоненциальной граница для линейного программирования" (PDF) , Algorithmica , 16 (4-5): 498-516, DOI : 10.1007 / BF01940877 , S2CID  877032.
  • Мегиддо, Нимрод (1983), "алгоритмы линейного времени для линейного программирования в R 3 и связанные с этим проблемы", SIAM журнал по вычислениям , 12 (4): 759-776, DOI : 10,1137 / 0212052 , МР  0721011 , S2CID  14467740.
  • Мегиддо, Нимрод (1984), "Линейное программирование в линейное время , когда размерность фиксируется", Журнал ACM , 31 (1): 114-127, DOI : 10,1145 / +2422,322418 , МР  0821388 , S2CID  12686747.
  • Нильсен, Франк; Нок, Ричард (2008), "О наименьшей информации вшита диска" (PDF) , Information Processing Letters , 105 (3): 93-97, DOI : 10.1016 / j.ipl.2007.08.007 , MR  2378119.
  • Пуэрто, Дж .; Родригес-Чиа, AM; Тамир, А. (2010), "О плоской кусочно - квадратичной задачи 1-центр", Algorithmica , 57 (2): 252-283, DOI : 10.1007 / s00453-008-9210-2 , МР  2587554 , S2CID  18587944.
  • Шарф, Герберт Э. (1977), "Наблюдение за структурой неделимых производственных множеств", Труды Национальной академии наук Соединенных Штатов Америки , 74 (9): 3637–3641, Bibcode : 1977PNAS .. .74.3637S , DOI : 10.1073 / pnas.74.9.3637 , МР  0452678 , КУП  431672 , PMID  16592435.
  • Сейдел, Раймунд (1991), "сделали Малую линейное программирование и выпуклые оболочки легко", Дискретная и Вычислительная геометрия , 6 (5): 423-434, DOI : 10.1007 / BF02574699 , МР  1115100.
  • Шарир, Миха ; Welzl, Emo (1992), "Комбинаторная оценка для линейного программирования и связанных с ним проблем", 9-й ежегодный симпозиум по теоретическим аспектам информатики (STACS), Кашан, Франция, 13–15 февраля 1992 г., Труды , Лекционные заметки по информатике , 577 , Springer-Verlag, стр 567-579,. DOI : 10.1007 / 3-540-55210-3_213.
  • Стикни, Алан; Уотсон, Лэйн (1978), "Digraph модель алгоритмов Бард-типа для линейной задачи дополнительности", Математика исследования операций , 3 (4): 322-333, DOI : 10.1287 / moor.3.4.322 , MR  0509668.
  • Сабо, Тибор; Welzl, Эмо (2001), "Уникальные ориентации раковины кубов" (PDF) , сорок второй IEEE симпозиум по Основы информатики (Лас - Вегас, штат Невада, 2001) , стр 547-555,. Дои : 10,1109 / SFCS.2001.959931 , MR  1948744 , S2CID  6597643.
  • Welzl, Emo (1991), «Наименьшие окружающие диски (шары и эллипсоиды)», в Maurer, H. (ed.), New Results and New Trends in Computer Science (PDF) , Lecture Notes in Computer Science (555 ed.) ., Springer-Verlag, стр 359-370, DOI : 10.1007 / BFb0038202.