Problem typu LP

W badaniu algorytmów problem typu LP (zwany także uogólnionym programem liniowym ) jest problemem optymalizacyjnym , który ma pewne właściwości wspólne z niskowymiarowymi programami liniowymi i który można rozwiązać za pomocą podobnych algorytmów. Problemy typu LP obejmują wiele ważnych problemów optymalizacyjnych, które same w sobie nie są programami liniowymi, takich jak problem znalezienia najmniejszego okręgu zawierającego dany zbiór punktów planarnych. Można je rozwiązać za pomocą kombinacji losowych algorytmów w określonym czasie liniowy pod względem liczby elementów definiujących problem i podwykładniczy w wymiarze problemu.

Definicja

Problemy typu LP zostały zdefiniowane przez Sharira i Welzla (1992) jako problemy, w których jako dane wejściowe podaje się skończony zbiór $S$ elementów oraz funkcję $f$ , która odwzorowuje podzbiory $S$ na wartości z całkowicie uporządkowanego zbioru. Funkcja musi spełniać dwie kluczowe właściwości:

Monotoniczność: dla każdych dwóch zbiorów $A \subseteq B \subseteq S$ , f ( A ) ≤ f ( B ) ≤ f ( S ).
Lokalność: dla każdych dwóch zbiorów $A \subseteq B \subseteq S$ i każdego elementu $x$ w $S$ , jeśli $f (A) = f (B) = f (A \cup {x})$ , to $f (A) = f (B \cup {x})$ .

Podstawą problemu typu LP jest zbiór $B \subseteq S$ z tą właściwością, że każdy właściwy podzbiór $B$ ma mniejszą wartość $f$ niż samo $B$ , a wymiar (lub wymiar kombinatoryczny ) problemu typu LP jest zdefiniowany jako będzie maksymalną licznością bazy.

Zakłada się, że algorytm optymalizacyjny może oceniać funkcję $f$ tylko na zbiorach, które same są bazami lub które powstają przez dodanie do bazy pojedynczego elementu. Alternatywnie, algorytm można ograniczyć do dwóch prymitywnych operacji: testu naruszenia , który określa, dla bazy $B$ i elementu $x$ , czy $f (B) = f (B \cup {x})$ , oraz obliczenia podstawy , które (z tym samym dane wejściowe) znajduje bazę $B \cup {x$ }. Zadaniem algorytmu jest oszacowanie $f (S)$ tylko przy użyciu tych ograniczonych ocen lub prymitywów.

Przykłady i zastosowania

Piłki LP

Program liniowy można zdefiniować za pomocą układu $d$ nieujemnych zmiennych rzeczywistych , podlegających $n$ liniowym ograniczeniom nierówności, wraz z nieujemną liniową funkcją celu, którą należy zminimalizować. Można to umieścić w ramach problemów typu LP, pozwalając $S$ być zbiorem ograniczeń i definiując $f (A)$ (dla podzbioru $A$ ograniczeń) jako minimalną wartość funkcji celu mniejszego programu liniowego zdefiniowanego przez $A$ . Przy odpowiednich ogólnych założeniach dotyczących pozycji (aby zapobiec temu, aby wiele punktów rozwiązania miało tę samą optymalną wartość funkcji celu), spełnia to wymagania monotoniczności i lokalności problemu typu LP i ma wymiar kombinatoryczny równy liczbie d $zmiennych$ . Podobnie program całkowitoliczbowy (składający się ze zbioru ograniczeń liniowych i liniowej funkcji celu, jak w programie liniowym, ale z dodatkowym ograniczeniem, że zmienne muszą przyjmować tylko wartości całkowite) spełnia zarówno właściwości monotoniczności, jak i lokalności problemu typu LP, z te same ogólne założenia dotyczące pozycji, jak dla programów liniowych. Twierdzenia Bella (1977) i Scarfa (1977) pokazują, że dla programu całkowitoliczbowego z $d$ zmiennymi wymiar kombinatoryczny wynosi co najwyżej $2 d$ .

Wiele naturalnych problemów optymalizacyjnych w geometrii obliczeniowej jest typu LP:

Problem najmniejszego koła

najmniejszego koła to problem znalezienia minimalnego promienia okręgu zawierającego dany zbiór $n$ punktów na płaszczyźnie. Spełnia monotoniczność (dodanie większej liczby punktów może tylko powiększyć okrąg) i lokalność (jeśli najmniejszy okrąg dla zbioru $A$ zawiera $B$ i $x$ , to ten sam okrąg zawiera również $B \cup {x$ }). Ponieważ najmniejszy okrąg jest zawsze określony przez jakieś trzy punkty, problem najmniejszego koła ma trzeci wymiar kombinatoryczny, mimo że jest zdefiniowany za pomocą dwuwymiarowej geometrii euklidesowej. Mówiąc bardziej ogólnie, najmniejsza otaczająca kula punktów w $d$ tworzą problem typu LP o wymiarze kombinatorycznym $d + 1$ . Problem najmniejszego koła można uogólnić na najmniejszą kulę zawierającą zestaw kul, na najmniejszą kulkę, która dotyka lub otacza każdy zestaw kul, na ważony problem 1-środka lub na podobne problemy z mniejszymi otaczającymi kulkami w nie- Przestrzenie euklidesowe, takie jak przestrzeń z odległościami określonymi przez dywergencję Bregmana . Powiązany problem znalezienia najmniejszej obejmującej elipsoidy jest również problemem typu LP, ale ma większy wymiar kombinatoryczny, $d (re + 3)/2$ .
Niech $0 K, K 1, ...$ będzie ciągiem $n$ zbiorów wypukłych w $d$ -wymiarowej przestrzeni euklidesowej i załóżmy, że chcemy znaleźć najdłuższy przedrostek tego ciągu, który ma wspólny punkt przecięcia. Można to wyrazić jako problem typu LP, w którym $f (A) = - i$ gdzie K _i jest pierwszym elementem A , który nie należy do przecinającego się przedrostka A , i gdzie $f (A) = - n$ jeśli nie ma takiego członka. Wymiar kombinatoryczny tego systemu to $d + 1$ .
Załóżmy, że mamy zbiór ustawionych w osi prostokątnych pudełek w trójwymiarowej przestrzeni i chcemy znaleźć linię skierowaną do dodatniej oktany przestrzeni, która przecina wszystkie pudełka. Można to wyrazić jako problem typu LP o kombinatorycznym wymiarze 4.
Problem znalezienia najbliższej odległości między dwoma wypukłymi polytopami , określonymi przez ich zbiory wierzchołków, można przedstawić jako problem typu LP. W tym sformułowaniu zbiór $S$ jest zbiorem wszystkich wierzchołków w obu polytopach, a wartość funkcji $f (A)$ jest negacją najmniejszej odległości między wypukłymi otoczkami dwóch podzbiorów $A$ wierzchołków w dwóch polytopach. Kombinatoryczny wymiar problemu to $d + 1,$ jeśli dwa polytopy są rozłączne, lub $d + 2$ , jeśli mają niepuste skrzyżowanie.
Niech $0 S = {f, f 1, ...$ } będzie zbiorem funkcji quasiwypukłych . Wówczas $max i fi jest punktowe$ maksimum $max i fi problemem$ jest samo w sobie quasi-wypukłe, a problem znalezienia minimalnej wartości typu LP. Ma wymiar kombinatoryczny co najwyżej $2 d + 1$ , gdzie $d$ jest wymiarem dziedziny funkcji, ale dla wystarczająco gładkich funkcji wymiar kombinatoryczny jest mniejszy, co najwyżej $re + 1$ . Wiele innych problemów typu LP można również wyrazić w ten sposób za pomocą funkcji quasi-wypukłych; $fi okręgu$ otaczającego jest problem minimalizacji $max i fi,$ gdzie każda z funkcji mierzy odległość euklidesową od jednego z podanych punktów.

Problemy typu LP zostały również wykorzystane do określenia optymalnych wyników niektórych gier w algorytmicznej teorii gier , poprawy rozmieszczenia wierzchołków w siatkach metody elementów skończonych , rozwiązania problemów lokalizacji obiektów , analizy złożoności czasowej niektórych algorytmów wyszukiwania w czasie wykładniczym i zrekonstruowania trójwymiarowe pozycje obiektów z ich dwuwymiarowych obrazów.

Algorytmy

Seidela

Seidel (1991) podał algorytm niskowymiarowego programowania liniowego, który można dostosować do struktury problemu typu LP. Algorytm Seidela przyjmuje jako dane wejściowe zbiór $S$ i oddzielny zbiór $X$ (początkowo pusty) elementów, o których wiadomo, że należą do bazy optymalnej. Następnie analizuje pozostałe elementy jeden po drugim w przypadkowej kolejności, przeprowadzając testy naruszeń dla każdego z nich i, w zależności od wyniku, wykonując rekurencyjne wywołanie tego samego algorytmu z większym zestawem znanych elementów podstawowych. Można to wyrazić następującym pseudokodem:

    
       funkcja  seidel(  S  ,  f  ,  X  )  to  R  := zbiór pusty  B  :=  X  dla  x  w losowej permutacji  S  :  if  (  B  ) ≠  f  (  B  ∪ {  x  }):  B :   =  seidel(  R  ,  fa  ,  X  ∪ {  x  })  R  :=  R   ∪ {  x  }  powrót  B

W problemie o kombinatorycznym wymiarze $d$ test łamania w i $-$ tej iteracji algorytmu kończy się niepowodzeniem tylko wtedy, gdy $x$ jest jednym z $d - | X |$ pozostałych elementów bazowych, co dzieje się co najwyżej z prawdopodobieństwem $(d - | X |)/ i$ . Na podstawie tych obliczeń można wykazać, że ogólnie oczekiwana liczba testów naruszeń przeprowadzonych przez algorytm wynosi $O(d! n)$ , liniowo w $n$ , ale gorzej niż wykładniczo w $re$ .

Clarksona

Clarkson (1995) definiuje dwa algorytmy, algorytm rekurencyjny i algorytm iteracyjny, do programowania liniowego opartego na technikach losowego próbkowania i sugeruje kombinację tych dwóch, która wywołuje algorytm iteracyjny z algorytmu rekurencyjnego. Algorytm rekurencyjny wielokrotnie wybiera losowe próbki, których rozmiar jest w przybliżeniu pierwiastkiem kwadratowym z rozmiaru wejściowego, rekurencyjnie rozwiązuje próbkowany problem, a następnie używa testów naruszenia, aby znaleźć podzbiór pozostałych elementów, który musi zawierać co najmniej jeden element podstawowy:

    
        
      funkcja  rekurencyjna(  S  ,  f  )  to  X  :=  powtórzenie zbioru pustego   R  := losowy podzbiór  S  o rozmiarze d√n  B  := baza dla  R  ∪  X  , obliczona rekurencyjnie  V  := {  x  |  fa  (  b  ) ≠  fa  (  b  ∪ {  x  })}  X  :=  X  ∪  V  do  V   jest pusty  powrót  B

W każdej iteracji oczekiwany rozmiar $V$ to $O(\sqrt n)$ , a zawsze, gdy $V$ jest niepuste, zawiera co najmniej jeden nowy element ostatecznej bazy $S$ . Dlatego algorytm wykonuje co najwyżej $iteracje$ , z których każda wykonuje $n$ testów naruszenia i wykonuje pojedyncze rekurencyjne wywołanie podproblemu o rozmiarze $O(d \sqrt n)$ .

Algorytm iteracyjny Clarksona przypisuje wagi każdemu elementowi $S$ , początkowo wszystkie są równe. Następnie wybiera losowo zbiór $R$ składający się z $9 d 2$ elementów z $S i oblicza zbiory$ $B$ i $V ,$ tak jak w poprzednim algorytmie. Jeśli całkowita waga $V$ jest co najwyżej $2/(9 d - 1)$ razy większa od całkowitej wagi $S$ (co dzieje się ze stałym prawdopodobieństwem), to algorytm podwaja wagi każdego elementu $V$ i tak jak poprzednio powtarza ten proces, aż $V$ stanie się pusty. W każdej iteracji można wykazać, że waga podstawy optymalnej rośnie szybciej niż całkowita waga $S$ , z czego wynika, że algorytm musi kończyć się w ciągu $O(log n)$ iteracji.

Wykorzystując algorytm rekurencyjny do rozwiązania danego problemu, przełączając się na algorytm iteracyjny dla jego wywołań rekurencyjnych, a następnie ponownie przełączając się na algorytm Seidela dla wywołań wykonywanych przez algorytm iteracyjny, możliwe jest rozwiązanie danego problemu typu LP za pomocą O $(dn + d! d O(1) log n)$ testy naruszenia.

W zastosowaniu do programu liniowego algorytm ten można interpretować jako metodę dual simplex . Z pewnymi dodatkowymi prymitywami obliczeniowymi poza testem naruszenia i podstawowymi prymitywami obliczeniowymi, metoda ta może być deterministyczna.

Matoušek, Sharir i Welzl

Matoušek, Sharir i Welzl (1996) opisują algorytm, który wykorzystuje dodatkową właściwość programów liniowych, która nie zawsze jest utrzymywana przez inne problemy typu LP, że wszystkie bazy mają tę samą liczność względem siebie. Jeśli problem typu LP nie ma tej właściwości, można go mieć, dodając $d$ nowych elementów fikcyjnych i modyfikując funkcję $f$ , aby zwracała uporządkowanej parze jej starą wartość $f (A)$ i liczbę $min (d, | A |)$ , uporządkowane leksykograficznie .

Zamiast dodawać elementy S pojedynczo lub znajdować próbki elementów, Matoušek, Sharir i Welzl (1996) opisują algorytm, który usuwa elementy pojedynczo. Na każdym kroku utrzymuje bazę $C$ , która początkowo może być zbiorem elementów fikcyjnych. Można to opisać następującym pseudokodem:

      
         
     
         funkcja  msw(  S  ,  f  ,  C  )  to  jeśli  S  =  C  to  zwróć  C  wybierz losowy element x z  S  \  C  B  = msw(  S  \  x  ,  f  ,  C  )  jeśli  f  (  B  ) ≠ f(B ∪ {x })  następnie  B  := podstawa(  B  ∪ {  x  })  B  := msw(   S  ,  fa  ,  B  )  powrót  B

W większości rekurencyjnych wywołań algorytmu test naruszenia kończy się powodzeniem i instrukcja if jest pomijana. Jednak z małym prawdopodobieństwem test łamania kończy się niepowodzeniem i algorytm wykonuje dodatkowe obliczenie bazy, a następnie dodatkowe wywołanie rekurencyjne. Jak pokazują autorzy, oczekiwany czas algorytmu jest liniowy w n i wykładniczy w pierwiastku kwadratowym z $d log n$ . Łącząc tę metodę z rekurencyjnymi i iteracyjnymi procedurami Clarksona, te dwie formy zależności od czasu można od siebie oddzielić, co daje algorytm wykonujący O ( dn ) testy naruszenia w zewnętrznym algorytmie rekurencyjnym i liczba, która jest wykładnicza w pierwiastku kwadratowym z $d log d$ na niższych poziomach algorytmu.

Wariacje

Optymalizacja z wartościami odstającymi

Matoušek (1995) rozważa odmianę problemów optymalizacyjnych typu LP, w których razem ze zbiorem $S$ i funkcją celu $f dana$ jest liczba $k$ ; zadaniem jest usunięcie $k$ elementów z $S$ , aby funkcja celu na pozostałym zbiorze była jak najmniejsza. Na przykład, po zastosowaniu do problemu najmniejszego koła, dałoby to najmniejsze koło, które zawiera wszystko oprócz $k$ danego zbioru punktów planarnych. Pokazuje, że dla wszystkich niezdegenerowanych problemów typu LP (tj. problemów, w których wszystkie podstawy mają różne wartości) problem ten można rozwiązać w czasie O( nk d $), rozwiązując zbiór$ O $(k d)$ LP -problemy typu zdefiniowane przez podzbiory $S$ .

Ukryte problemy

Niektóre problemy optymalizacji geometrycznej można wyrazić jako problemy typu LP, w których liczba elementów w sformułowaniu typu LP jest znacznie większa niż liczba wartości danych wejściowych dla problemu optymalizacji. Jako przykład rozważmy zbiór $n$ punktów na płaszczyźnie, z których każdy porusza się ze stałą prędkością. W dowolnym momencie średnica tego układu jest maksymalną odległością między dwoma jego punktami. Problem znalezienia czasu, w którym średnica jest minimalizowana, można sformułować jako minimalizację punktowego maksimum $O(n 2)$ funkcje kwaziwypukłe, po jednej dla każdej pary punktów, mierzące odległość euklidesową między parą w funkcji czasu. Zatem można go rozwiązać jako problem typu LP o kombinatorycznym wymiarze dwa na zbiorze $O(n 2)$ , ale zbiór ten jest znacznie większy niż liczba punktów wejściowych.

Chan (2004) opisuje algorytm rozwiązywania niejawnie zdefiniowanych problemów typu LP, takich jak ten, w którym każdy element typu LP jest określony przez k $-$ krotkę wartości wejściowych dla pewnej stałej $k$ . Aby zastosować jego podejście, musi istnieć $algorytm$ decyzyjny , który może określić, dla danej bazy $B typu LP$ i zbioru $S$ n wartości wejściowych, czy $B$ jest bazą dla problemu typu LP określonego przez $S$ .

Algorytm Chana wykonuje następujące kroki:

Jeśli liczba wartości wejściowych jest poniżej pewnej wartości progowej, znajdź zestaw elementów typu LP, który określa i rozwiąż wynikowy jawny problem typu LP.
W przeciwnym razie podziel wartości wejściowe na odpowiednią liczbę większą od $k$ równych podzbiorów $S i$ .
Jeśli $f$ jest funkcją celu dla niejawnie zdefiniowanego problemu typu LP, który ma zostać rozwiązany, to zdefiniuj funkcję $g$ , która odwzorowuje zbiory podzbiorów $Si na$ wartość $f$ na sumie zbioru. Wówczas zbiór podzbiorów $S i$ oraz sama funkcja celu $g$ definiuje problem typu LP, o tym samym wymiarze co uwikłany problem do rozwiązania.
Rozwiąż (jawny) problem typu LP zdefiniowany przez $g$ za pomocą algorytmu Clarksona, który przeprowadza liniową liczbę testów naruszenia i polilogarytmiczną liczbę ocen bazowych. Oceny bazowe dla $g$ mogą być wykonywane przez rekurencyjne wywołania algorytmu Chana, a testy łamania przez wywołania algorytmu decyzyjnego.

Przy założeniu, że algorytm decyzyjny zajmuje pewien czas $O(T (n))$ , który rośnie co najmniej wielomianowo jako funkcja wielkości wejściowej $n$ , Chan pokazuje, że próg przełączania na jawne sformułowanie LP i liczba podzbiorów w podziale można wybrać w taki sposób, aby niejawny algorytm optymalizacji typu LP działał również w czasie $O(T (n))$ .

Na przykład dla minimalnej średnicy ruchomych punktów algorytm decyzyjny musi jedynie obliczyć średnicę zestawu punktów w ustalonym czasie, problem, który można rozwiązać w czasie O $(n log n) za pomocą techniki$ obrotowych suwmiarek . Dlatego algorytm Chana do znajdowania czasu, w którym średnica jest minimalizowana, również wymaga czasu $O(n log n)$ . Chan używa tej metody, aby znaleźć punkt o maksymalnej głębokości Tukeya wśród danego zbioru $n$ punktów w $d$ -wymiarowa przestrzeń euklidesowa w czasie $O(n d - 1 + n log n)$ . Podobną technikę zastosowali Braß, Heinrich-Litan i Morin (2003) , aby znaleźć punkt o maksymalnej głębokości Tukeya dla rozkładu jednorodnego na wypukłym wielokącie.

Historia i problemy z nią związane

Odkrycie liniowych algorytmów czasu dla programowania liniowego i obserwacja, że te same algorytmy mogą w wielu przypadkach być użyte do rozwiązywania problemów optymalizacji geometrycznej, które nie były programami liniowymi, sięga co najmniej Megiddo (1983, 1984), który podał liniowy oczekiwany czas algorytm zarówno dla programów liniowych z trzema zmiennymi, jak i problemu najmniejszego koła. Jednak Megiddo sformułował uogólnienie programowania liniowego raczej geometrycznie niż kombinatorycznie, jako optymalizacji wypukłej , a nie abstrakcyjny problem dotyczący systemów zbiorów. Podobnie Dyer (1986) i Clarkson (w wersji konferencyjnej Clarkson 1995 z 1988 r .) zauważyli, że ich metody można zastosować zarówno do programów wypukłych, jak i programów liniowych. Dyer (1992) wykazał, że problem minimalnej elipsoidy obejmującej można również sformułować jako problem optymalizacji wypukłej, dodając niewielką liczbę ograniczeń nieliniowych. Pionierami zastosowania randomizacji w celu poprawy ograniczeń czasowych dla niskowymiarowego programowania liniowego i powiązanych problemów byli Clarkson oraz Dyer i Frieze (1989) .

Definicja problemów typu LP w kategoriach funkcji spełniających aksjomaty lokalności i monotoniczności pochodzi od Sharira i Welzla (1992) , ale inni autorzy w tym samym przedziale czasowym sformułowali alternatywne kombinatoryczne uogólnienia programów liniowych. Na przykład w modelu opracowanym przez Gärtnera (1995) funkcja $f$ jest zastąpiona całkowitym uporządkowaniem podzbiorów $S$ . Możliwe jest zerwanie więzi w problemie typu LP w celu stworzenia porządku totalnego, ale tylko kosztem wzrostu wymiaru kombinatorycznego. Dodatkowo, podobnie jak w problemach typu LP, Gärtner definiuje pewne prymitywy do wykonywania obliczeń na podzbiorach elementów; jego formalizacja nie ma jednak odpowiednika wymiaru kombinatorycznego.

Inne abstrakcyjne uogólnienie zarówno programów liniowych, jak i problemów liniowej komplementarności , sformułowane przez Stickneya i Watsona (1978) , a później zbadane przez kilku innych autorów, dotyczy orientacji krawędzi hipersześcianu z tą właściwością, że każda ściana hipersześcianu (w tym cały hipersześcian jako twarz) ma unikalny zlew , wierzchołek bez wychodzących krawędzi. Orientacja tego typu może być utworzona z problemu typu LP przez odpowiednie podzbiory S z wierzchołkami hipersześcianu w taki sposób, że dwa podzbiory różnią się pojedynczym elementem wtedy i tylko wtedy, gdy odpowiednie wierzchołki są przyległe, oraz przez zorientowanie krawędzi między sąsiednimi zbiorami A ⊆ $B w kierunku$ B $,$ jeśli $f (A) \neq f (B)$ i w kierunku $A$ inaczej. Otrzymana orientacja ma dodatkową właściwość polegającą na tym, że tworzy skierowany graf acykliczny , z którego można wykazać, że losowy algorytm może znaleźć unikalne ujście całego hipersześcianu (optymalna podstawa problemu typu LP) w wielu krokach wykładniczych w pierwiastku kwadratowym z $n$ .

Niedawno opracowane ramy przestrzeni naruszających uogólniają problemy typu LP w tym sensie, że każdy problem typu LP może być modelowany przez przestrzeń naruszającą, ale niekoniecznie odwrotnie. Przestrzenie naruszające są definiowane podobnie do problemów typu LP, przez funkcję $f$ , która odwzorowuje zbiory na wartości funkcji celu, ale wartości $f$ nie są uporządkowane. Mimo braku zamawiania każdy zestaw $S$ ma dobrze zdefiniowany zestaw baz (zbiory minimalne o tej samej wartości co cały zbiór), które można znaleźć za pomocą odmian algorytmów Clarksona dla problemów typu LP. Rzeczywiście, wykazano, że przestrzenie naruszające dokładnie charakteryzują systemy, które można rozwiązać za pomocą algorytmów Clarksona.

Notatki

Amenta, Nina (1994), „Twierdzenia typu Helly'ego i uogólnione programowanie liniowe” (PDF) , Discrete and Computational Geometry , 12 (3): 241–261, doi : 10.1007 / BF02574379 , MR 1298910 , S2CID 26667725 .
Amenta, Nina ; Berno, Marshall; Eppstein, David (1999), „Optymalne rozmieszczenie punktów do wygładzania siatki”, Journal of Algorithms , 30 (2): 302–322, arXiv : cs.CG/9809081 , doi : 10.1006/jagm.1998.0984 , MR 1671836 , S2CID 182728 .
Bell, David E. (1977), „Twierdzenie dotyczące sieci liczb całkowitych” (PDF) , Studies in Applied Mathematics , 56 (2): 187–188, doi : 10,1002 / sapm1977562187 , MR 0462617 .
Brass, Piotr; Heinrich-Litan, Laura; Morin, Pat (2003), „Obliczanie środka obszaru wypukłego wielokąta” (PDF) , International Journal of Computational Geometry & Applications , 13 (5): 439–445, doi : 10.1142 / S021819590300127X , MR 2012837 .
Brise, Yves; Gärtner , Bernd (2011), „Algorytm Clarksona dla przestrzeni gwałcicieli” ( PDF) , Geometria obliczeniowa: teoria i zastosowania , 44 (2): 70–81 , arXiv : 0906.4706 MR 2737285 , S2CID 1233875 .
Chan, Timothy M. (2004), „Optymalny algorytm z randomizacją dla maksymalnej głębokości Tukeya” (PDF) , Proc. 15 Symp. ACM-SIAM Dyskretne algorytmy , s. 423–429 .
Chazelle, Bernard ; Matoušek, Jiří (1996), „O algorytmach deterministycznych w czasie liniowym dla problemów optymalizacji w ustalonym wymiarze” (PDF) , Journal of Algorithms , 21 (3): 579–597, doi : 10.1006/jagm.1996.0060 , MR 1417665 , S2CID 2482481 .
Clarkson, Kenneth L. (1995), „Algorytmy Las Vegas do programowania liniowego i całkowitoliczbowego, gdy wymiar jest mały” (PDF) , Journal of the ACM , 42 (2): 488–499, doi : 10.1145/201019.201036 , MR 1409744 , S2CID 6953625 .
Dyer, Martin E. (1986), „O wielowymiarowej technice wyszukiwania i jej zastosowaniu do euklidesowego problemu z jednym centrum”, SIAM Journal on Computing , 15 (3): 725–738, doi : 10.1137/0215052 , MR 0850419 .
Dyer, Martin E. (1992), „Klasa programów wypukłych z zastosowaniami do geometrii obliczeniowej”, Proc. 8th Symposium on Computational Geometry (SCG '92) , Berlin, Niemcy, s. 9–15, doi : 10.1145/142675.142681 , ISBN 0-89791-517-8 , S2CID 7654513 .
Dyer, Martin E.; Frieze, Alan M. (1989), „Losowy algorytm do programowania liniowego o stałych wymiarach”, Programowanie matematyczne , (Ser. A), 44 (2): 203–212, doi : 10.1007 / BF01587088 , MR 1003560 , S2CID 206800147 .
Eppstein, David (2005), „Programowanie kwaziwypukłe”, w: Goodman, Jacob E.; Pach, János ; Welzl, Emo (red.), Kombinatoryczna i obliczeniowa geometria , MSRI Publications, tom. 52, Uniwersytet Cambridge Prasa, s. 287–331, arXiv : cs.CG/0412046 , MR 2178325 .
Eppstein, David (2006), „Analiza Quasiconvex wielowymiarowych równań rekurencyjnych dla algorytmów śledzenia wstecznego”, ACM Transactions on Algorithms , 2 (4): 492–509, arXiv : cs.DS/0304018 , doi : 10.1145/1198513.1198515 , MR 2284242 , S2CID 9980061 .
Fischer, Kaspar; Gärtner, Bernd (2004), „Najmniejsza otaczająca kula piłek: struktura kombinatoryczna i algorytmy” (PDF) , International Journal of Computational Geometry & Applications , 14 (4–5): 341–378, doi : 10.1142 / S0218195904001500 , MR 2087827 .
Gärtner, Bernd (1995), „Algorytm podwykładniczy dla abstrakcyjnych problemów optymalizacji” (PDF) , SIAM Journal on Computing , 24 (5): 1018–1035, doi : 10.1137 / S0097539793250287 , MR 1350756 .
Gartner, Bernd; Matoušek, Jiří ; Rust, L.; Škovroň, P. (2008), „Przestrzenie naruszające: struktura i algorytmy”, Discrete Applied Mathematics , 156 (11): 2124–2141, arXiv : cs.DM/0606087 , doi : 10.1016/j.dam.2007.08.048 , MR 2437006 .
Gartner, Bernd; Welzl, Emo (2001), „Prosty lemat próbkowania: analiza i zastosowania w optymalizacji geometrycznej” (PDF) , Discrete and Computational Geometry , 25 (4): 569–590, doi : 10.1007 / s00454-001-0006-2 , MR 1838420 , S2CID 14263014 .
Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1996), „Szybkie algorytmy rozwiązywania problemów kolizji i bliskości z udziałem poruszających się obiektów geometrycznych”, Computational Geometry. Teoria i zastosowania , 6 (6): 371–391, doi : 10.1016/0925-7721(95)00028-3 , hdl : 11858/00-001M-0000-0014-B50E-D , MR 1415267 .
Halman, Nir (2007), „Proste gry stochastyczne, gry z parzystością, gry ze średnią wypłatą i gry z obniżoną wypłatą to problemy typu LP” , Algorithmica , 49 (1): 37–50, doi : 10.1007 / s00453-007-0175 -3 , MR 2344393 , S2CID 8183965 .
Kalai, Gil (1992), „Algorytm subwykładniczy z randomizacją simpleks”, Proc. 24th ACM Symposium on Theory of Computing , s. 475–482, doi : 10.1145/129712.129759 , S2CID 17447465 .
Li, Hongdong (2007), „Praktyczny algorytm triangulacji $L \infty$ z wartościami odstającymi”, Proc. Konf. IEEE on Computer Vision and Pattern Recognition (CVPR '07) , s. 1–8, doi : 10.1109/CVPR.2007.383068 , hdl : 1885/39190 , S2CID 14882916 .
Löffler, Maarten; van Kreveld, Marc (2010), „Największa ramka ograniczająca, najmniejsza średnica i powiązane problemy dotyczące nieprecyzyjnych punktów” (PDF) , Computational Geometry Theory and Applications , 43 (4): 419–433, doi : 10.1016/j.comgeo. 2009.03.007 , MR 2575803 .
Matoušek, Jiří (1995), „O optymalizacji geometrycznej z kilkoma naruszonymi ograniczeniami”, Discrete and Computational Geometry , 14 (4): 365–384, doi : 10.1007 / BF02570713 , MR 1360943 .
Matoušek, Jiří (2009), „Powrót do usuwania degeneracji w problemach typu LP”, Discrete and Computational Geometry , 42 (4): 517–526, doi : 10.1007 / s00454-008-9085-7 , MR 2556452 .
Matoušek, Jiří ; Szarir, Michał ; Welzl, Emo (1996), „Podwykładnicza granica programowania liniowego” (PDF) , Algorithmica , 16 (4–5): 498–516, doi : 10.1007 / BF01940877 , S2CID 877032 .
Megiddo, Nimrod (1983), „Algorytmy czasu liniowego do programowania liniowego w $R 3$ i problemy pokrewne”, SIAM Journal on Computing , 12 (4): 759–776, doi : 10.1137/0212052 , MR 0721011 , S2CID 14467740 .
Megiddo, Nimrod (1984), „Programowanie liniowe w czasie liniowym, gdy wymiar jest ustalony”, Journal of the ACM , 31 (1): 114–127, doi : 10.1145/2422.322418 , MR 0821388 , S2CID 12686747 .
Nielsen, Frank; Nock, Richard (2008), „Na najmniejszym otaczającym dysku informacyjnym” (PDF) , Information Processing Letters , 105 (3): 93–97, doi : 10.1016 / j.ipl.2007.08.007 , MR 2378119 .
Puerto, J.; Rodríguez-Chía, AM; Tamir, A. (2010), „Na planarnym, fragmentarycznie kwadratowym 1-centralnym problemie”, Algorithmica , 57 (2): 252–283, doi : 10.1007 / s00453-008-9210-2 , MR 2587554 , S2CID 18587944 .
Szalik, Herbert E. (1977), „Obserwacja struktury zbiorów produkcyjnych z niepodzielnościami”, Proceedings of the National Academy of Sciences of the United States of America , 74 (9): 3637–3641, Bibcode : 1977PNAS .. .74.3637S , doi : 10.1073/pnas.74.9.3637 , MR 0452678 , PMC 431672 , PMID 16592435 .
Seidel, Raimund (1991), „Łatwe programowanie liniowe w małych wymiarach i wypukłe kadłuby”, Discrete and Computational Geometry , 6 (5): 423–434, doi : 10.1007 / BF02574699 , MR 1115100 .
Szarir, Michał ; Welzl, Emo (1992), „Kombinatoryczna granica programowania liniowego i problemów pokrewnych”, 9. doroczne sympozjum poświęcone teoretycznym aspektom informatyki (STACS), Cachan, Francja, 13–15 lutego 1992 r., Proceedings , Lecture Notes in Computer Science , tom. 577, Springer-Verlag, s. 567–579, doi : 10.1007/3-540-55210-3_213 .
Stickney, Alan; Watson, Layne (1978), „Digraficzne modele algorytmów typu Barda dla problemu liniowej komplementarności”, Mathematics of Operations Research , 3 (4): 322–333, doi : 10.1287/moor.3.4.322 , MR 0509668 .
Szabo, Tibor; Welzl, Emo (2001), „Unikalne orientacje kostek zlewu” (PDF) , 42. IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) , s. 547–555, doi : 10.1109/SFCS.2001.959931 , MR 1948744 , S2CID 6597643 .
Welzl, Emo (1991), „Najmniejsze dyski otaczające (kule i elipsoidy)”, w: Maurer, H. (red.), Nowe wyniki i nowe trendy w informatyce (PDF) , Notatki z wykładów z informatyki (wyd. 555) , Springer-Verlag, s. 359–370, doi : 10.1007/BFb0038202 .