LP -type problem - LP-type problem

I studiet av algoritmer er et LP-problem (også kalt et generalisert lineært program ) et optimaliseringsproblem som deler visse egenskaper med lavdimensjonale lineære programmer, og som kan løses med lignende algoritmer. Problemer av LP-type inkluderer mange viktige optimaliseringsproblemer som ikke i seg selv er lineære programmer, for eksempel problemet med å finne den minste sirkelen som inneholder et gitt sett med plane punkter. De kan løses ved en kombinasjon av randomiserte algoritmer i en tidsperiode som er lineær i antall elementer som definerer problemet, og supexponential i dimensjonen av problemet.

Definisjon

LP-type problemer ble definert av Sharir & Welzl (1992) som problemer der man som input får et begrenset sett $S$ med elementer, og en funksjon $f$ som tilordner undersett av $S$ til verdier fra et totalt ordnet sett. Funksjonen er nødvendig for å tilfredsstille to viktige egenskaper:

Monotonicitet: for hvert annet sett $A \subseteq B \subseteq S$ , f ( A ) ≤ f ( B ) ≤ f ( S ).
Lokalitet: for hvert to sett $A \subseteq B \subseteq S$ og hvert element $x$ i $S$ , hvis $f (A) = f (B) = f (A \cup {x})$ , så $f (A) = f (B \cup {x})$ .

Et grunnlag for et problem av LP-typen er et sett $B \subseteq S$ med egenskapen at hver riktig undersett av $B$ har en mindre verdi på $f$ enn $B$ selv, og dimensjonen (eller kombinatorisk dimensjon ) av et LP-type problem er definert til være den maksimale kardinaliteten til et grunnlag.

Det antas at en optimaliseringsalgoritme bare kan evaluere funksjonen $f$ på sett som selv er baser eller som dannes ved å legge et enkelt element til et grunnlag. Alternativt kan algoritmen være begrenset til to primitive operasjoner: en overtredelsestest som for basis $B$ og element $x$ avgjør om $f (B) = f (B \cup {x})$ , og en grunnberegning som (med samme innganger) finner et grunnlag for $B \cup {x$ }. Oppgaven for algoritmen å utføre er å evaluere $f (S)$ ved å bare bruke disse begrensede evalueringene eller primitivene.

Eksempler og applikasjoner

Spill media

Lp Balls

Et lineært program kan defineres av et system med $d$ ikke-negative reelle variabler , underlagt $n$ lineære ulikhetsbegrensninger, sammen med en ikke-negativ lineær objektivfunksjon som skal minimeres. Dette kan plasseres i rammen av problemer av LP-type ved å la $S$ være settet med begrensninger, og definere $f (A)$ (for en delmengde $A$ av begrensningene) til å være den minste objektive funksjonsverdien til det mindre lineære programmet definert av $A$ . Med passende generelle posisjonsforutsetninger (for å forhindre at flere løsningspunkter har den samme optimale objektive funksjonsverdien), tilfredsstiller dette monotonicitet og lokalitetskravene til et LP-problem, og har kombinatorisk dimensjon lik antallet $d$ av variabler. På samme måte tilfredsstiller et heltallsprogram (bestående av en samling lineære begrensninger og en lineær objektivfunksjon, som i et lineært program, men med den ytterligere begrensningen som variablene bare må ta heltallverdier) både monotonien og lokalitetsegenskapene til en LP -type problem, med de samme generelle posisjonsforutsetningene som for lineære programmer. Teoremer fra Bell (1977) og Scarf (1977) viser at for et heltallsprogram med $d$ -variabler er den kombinatoriske dimensjonen høyst $2 d$ .

Mange naturlige optimaliseringsproblemer i beregningsgeometri er LP-type:

Minste sirkelproblem

Det minste sirkelproblemet er problemet med å finne minimumsradiusen til en sirkel som inneholder et gitt sett med $n$ punkter i planet. Den tilfredsstiller monotoniciteten (å legge til flere punkter kan bare gjøre sirkelen større) og lokalitet (hvis den minste sirkelen for sett $A$ inneholder $B$ og $x$ , inneholder den samme sirkelen også $B \cup {x$ }). Fordi den minste sirkelen alltid bestemmes av noen tre punkter, har den minste sirkelproblemet kombinatorisk dimensjon tre, selv om den er definert ved hjelp av todimensjonal euklidisk geometri. Mer generelt danner den minste omsluttende ballen av punkter i $d$ dimensjoner et LP-problem med kombinatorisk dimensjon $d + 1$ . Det minste sirkelproblemet kan generaliseres til den minste ballen som omslutter et sett med baller, til den minste ballen som berører eller omgir hver av et sett med baller, til det veide 1-senterproblemet eller til lignende mindre omsluttende ballproblemer i ikke- Euklidiske mellomrom som rommet med avstander definert av Bregman -divergens . Det relaterte problemet med å finne den minste omsluttende ellipsoiden er også et LP-problem, men med en større kombinatorisk dimensjon, $d (d + 3)/2$ .
La $K 0, K 1, ...$ være en sekvens av $n$ konvekse sett i $d$ -dimensjonale euklidiske rom, og anta at vi ønsker å finne det lengste prefikset for denne sekvensen som har et felles skjæringspunkt. Dette kan uttrykkes som et LP-problem der $f (A) = -i$ hvor K _i er det første medlemmet i A som ikke tilhører et kryssende prefiks av A , og hvor $f (A) = -n$ hvis det er ikke et slikt medlem. Den kombinatoriske dimensjonen til dette systemet er $d + 1$ .
Anta at vi får en samling av aksejusterte rektangulære bokser i tredimensjonalt rom, og ønsker å finne en linje rettet inn i den positive oktanten av plass som skjærer gjennom alle boksene. Dette kan uttrykkes som et LP-problem med kombinatorisk dimensjon 4.
Problemet med å finne den nærmeste avstanden mellom to konvekse polytoper , spesifisert av deres sett med hjørner, kan representeres som et LP-problem. I denne formuleringen er settet $S$ settet av alle toppunktene i begge polytoper, og funksjonsverdien $f (A)$ er negasjonen av den minste avstanden mellom de konvekse skrogene til de to undersettene $A$ av toppunktene i de to polytopene. Den kombinatoriske dimensjonen til problemet er $d + 1$ hvis de to polytopene er usammenhengende, eller $d + 2$ hvis de har et ikke -ledig kryss.
La $S = {f 0, f 1, ...$ } være et sett med kvasikonvekse funksjoner . Da er punktvis maksimal $maks i f i$ seg selv kvasikonveks, og problemet med å finne minimumsverdien til $max i f i$ er et LP-problem. Den har en kombinatorisk dimensjon på maksimalt $2 d + 1$ , hvor $d$ er dimensjonen til domenet til funksjonene, men for tilstrekkelig jevne funksjoner er den kombinatoriske dimensjonen mindre, høyst $d + 1$ . Mange andre problemer av LP-typen kan også uttrykkes ved bruk av kvasikonvekse funksjoner på denne måten; for eksempel er det minste omsluttende sirkelproblemet problemet med å minimere $maks i f i$ hvor hver av funksjonene $f i$ måler den euklidiske avstanden fra et av de gitte punktene.

Problemer av LP-type har også blitt brukt til å bestemme de optimale resultatene av visse spill i algoritmisk spillteori , forbedre toppunktplassering i endelige elementmetode masker, løse anleggslokaliseringsproblemer , analysere tidskompleksiteten til visse eksponentielle tidssøkalgoritmer og rekonstruere tredimensjonale posisjoner av objekter fra deres todimensjonale bilder.

Algoritmer

Seidel

Seidel (1991) ga en algoritme for lavdimensjonal lineær programmering som kan tilpasses LP-type problemramme. Seidels algoritme tar som input settet $S$ og et separat sett $X$ (opprinnelig tomt) av elementer som er kjent for å tilhøre det optimale grunnlaget. Den vurderer deretter de gjenværende elementene en-for-en i en tilfeldig rekkefølge, utfører overtredelsestester for hver enkelt og, avhengig av resultatet, utfører et rekursivt anrop til den samme algoritmen med et større sett med kjente grunnelementer. Det kan uttrykkes med følgende pseudokode:

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, basis(X ∪ {x}))
        R := R ∪ {x}
    return B

I et problem med kombinatorisk dimensjon $d$ , brudd test i $jeg$ th iterasjon av algoritmen svikter bare når $x$ er en av $d - | X |$ gjenværende basiselementer, som skjer med høyst sannsynlighet $(d - | X |)/ i$ . Basert på denne beregningen kan det vises at samlet forventet antall overtredelsestester utført av algoritmen er $O (d! N)$ , lineær i $n$ men verre enn eksponentiell i $d$ .

Clarkson

Clarkson (1995) definerer to algoritmer, en rekursiv algoritme og en iterativ algoritme, for lineær programmering basert på random sampling teknikker, og foreslår en kombinasjon av de to som kaller den iterative algoritmen fra den rekursive algoritmen. Den rekursive algoritmen velger gjentatte ganger tilfeldige prøver hvis størrelse er omtrent kvadratroten til inngangsstørrelsen, løser det samplede problemet rekursivt, og bruker deretter bruddstester for å finne et delsett av de gjenværende elementene som må inneholde minst ett basiselement:

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

I hver iterasjon, den forventede størrelsen av $V$ er $O (\sqrt n)$ , og når $V$ er ikketom det innbefatter minst ett nytt element av den endelige basis av $S$ . Derfor utfører algoritmen maksimalt $d$ iterasjoner, som hver utfører $n$ overtredelsestester og foretar et enkelt rekursivt anrop til et delproblem av størrelse $O (d \sqrt n)$ .

Clarksons iterative algoritme tildeler vekt til hvert element i $S$ , i utgangspunktet er alle like. Den velger deretter et sett $R$ på $9 d 2$ elementer fra $S$ tilfeldig, og beregner settene $B$ og $V$ som i den forrige algoritmen. Hvis den totale vekten av $V$ er maksimalt $2/(9 d - 1)$ ganger totalvekten til $S$ (som skjer med konstant sannsynlighet), dobler algoritmen vektene til hvert element av $V$ , og som før gjentar denne prosessen til $V$ blir tom. I hver iterasjon kan det vises at vekten av det optimale grunnlaget øker med en større hastighet enn den totale vekten av $S$ , hvorav det følger at algoritmen må avsluttes innenfor $O (log n)$ iterasjoner.

Ved å bruke den rekursive algoritmen til å løse et gitt problem, bytte til den iterative algoritmen for dens rekursive samtaler, og deretter bytte igjen til Seidels algoritme for samtalene fra den iterative algoritmen, er det mulig å løse et gitt LP-problem med $O (dn + d! d O (1) log n)$ overtredelsestester.

Når den brukes på et lineært program, kan denne algoritmen tolkes som en dual simplex -metode . Med visse ekstra beregningsprimitiver utover overtredelsestesten og basisberegningsprimitiver, kan denne metoden gjøres deterministisk.

Matoušek, Sharir og Welzl

Matoušek, Sharir & Welzl (1996) beskriver en algoritme som bruker en ekstra egenskap for lineære programmer som ikke alltid er besatt av andre LP-problemer, at alle baser har samme kardinalitet som hverandre. Hvis et problem av LP-typen ikke har denne egenskapen, kan du få det ved å legge til $d$ nye dummy-elementer og ved å endre funksjonen $f for$ å returnere det bestilte paret med den gamle verdien $f (A)$ og tallet $min (d, | A |)$ , ordnet leksikografisk .

I stedet for å legge til elementer av S en om gangen, eller finne prøver av elementene, beskriver Matoušek, Sharir & Welzl (1996) en algoritme som fjerner elementer ett om gangen. Ved hvert trinn opprettholder den et grunnlag $C$ som i utgangspunktet kan være settet med dummy -elementer. Det kan beskrives med følgende pseudokode:

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

I de fleste av de rekursive anropene til algoritmen lykkes overtredelsestesten og if -setningen hoppes over. Imidlertid mislykkes bruddstesten med en liten sannsynlighet, og algoritmen foretar en ekstra beregning og deretter en ekstra rekursiv samtale. Som forfatterne viser, er den forventede tiden for algoritmen lineær i n og eksponentiell i kvadratroten til $d log n$ . Ved å kombinere denne metoden med Clarksons rekursive og iterative prosedyrer, kan disse to formene for tidsavhengighet skilles fra hverandre, noe som resulterer i en algoritme som utfører O ( dn ) bruddstester i den ytre rekursive algoritmen og et tall som er eksponentielt i kvadratrot av $d log d$ i de lavere nivåene av algoritmen.

Variasjoner

Optimalisering med outliers

Matoušek (1995) vurderer en variasjon av LP-type optimaliseringsproblemer der man sammen med settet $S$ og objektivfunksjonen $f$ får et tall $k$ ; oppgaven er å fjerne $k$ -elementer fra $S$ for å gjøre objektivfunksjonen på det gjenværende settet så lite som mulig. For eksempel, når det brukes på det minste sirkelproblemet, vil dette gi den minste sirkelen som inneholder alle unntatt $k$ av et gitt sett med plane punkter. Han viser at for alle ikke-degenererte problemer av LP-type (det vil si problemer der alle baser har forskjellige verdier) kan dette problemet løses i tide $O (nk d)$ , ved å løse et sett med $O (k d)$ LP -type problemer som defineres av undergrupper av $S$ .

Implisitte problemer

Noen geometriske optimaliseringsproblemer kan uttrykkes som LP-type problemer der antall elementer i LP-typeformuleringen er betydelig større enn antall inngangsdataverdier for optimaliseringsproblemet. Som et eksempel kan du vurdere en samling av $n$ punkter i planet, som hver beveger seg med konstant hastighet. Når som helst er diameteren på dette systemet maksimal avstand mellom to av punktene. Problemet med å finne et tidspunkt der diameteren er minimert, kan formuleres som å minimere det punktvise maksimumet for $O (n 2)$ kvasikonvekse funksjoner, en for hvert parpar, som måler den euklidiske avstanden mellom paret som en funksjon av tiden. Dermed kan det løses som et LP-problem med kombinatorisk dimensjon to på et sett med $O (n 2)$ elementer, men dette settet er betydelig større enn antall inngangspunkter.

Chan (2004) beskriver en algoritme for å løse implisitt definerte problemer av LP-typen slik som denne der hvert element av LP-typen bestemmes av en $k-$ dobbel av inngangsverdier, for noen konstante $k$ . For å kunne anvende hans metode, må det eksistere et desisjonsalgoritme som kan bestemme, for en gitt LP-type basis $B$ og sett $S$ av $n-$ inngangsverdier, hvorvidt $B$ er en basis for LP-type problem bestemt ved $S$ .

Chans algoritme utfører følgende trinn:

Hvis antallet inngangsverdier er under en terskelverdi, finner du settet med elementer av LP-typen som det bestemmer og løser det resulterende eksplisitte LP-type problemet.
Ellers del inndataverdiene i et passende tall større enn $k$ av like store undersett $S i$ .
Hvis $f$ er den objektive funksjonen for det implisitt definerte problemet av LP-typen som skal løses, definerer du en funksjon $g$ som kartlegger samlinger av delsett $S i$ til verdien av $f$ på foreningen av samlingen. Deretter definerer samlingen av delsett $S i$ og selve objektivfunksjonen $g$ et LP-problem, av samme dimensjon som det implisitte problemet som skal løses.
Løs det (eksplisitte) LP-type problemet definert av $g$ ved å bruke Clarksons algoritme, som utfører et lineært antall overtredelsestester og et polylogaritmisk antall basisevalueringer. Basisevalueringene for $g$ kan utføres ved rekursive samtaler til Chans algoritme, og overtredelsestestene kan utføres ved å ringe til beslutningsalgoritmen.

Med forutsetningen om at beslutningsalgoritmen tar en tid $O (T (n))$ som vokser minst polynomisk som en funksjon av inngangsstørrelsen $n$ , viser Chan at terskelen for å bytte til en eksplisitt LP -formulering og antall undersett i partisjonen kan velges på en slik måte at den implisitte optimeringsalgoritmen av LP-typen også kjører i tiden $O (T (n))$ .

For eksempel, for minste diameter på bevegelige punkter, trenger beslutningsalgoritmen bare å beregne diameteren til et sett med punkter på et bestemt tidspunkt, et problem som kan løses i $O (n log n)$ tid ved hjelp av roterende kaliperteknikk . Derfor tar Chans algoritme for å finne tidspunktet da diameteren minimeres også tid $O (n log n)$ . Chan bruker denne metoden for å finne et punkt med maksimal Tukey -dybde blant en gitt samling av $n$ punkter i $d$ -dimensjonalt euklidisk rom, i tid $O (n d -1 + n log n)$ . En lignende teknikk ble brukt av Braß, Heinrich-Litan & Morin (2003) for å finne et punkt med maksimal Tukey-dybde for jevn fordeling på en konveks polygon.

Historie og relaterte problemer

Oppdagelsen av lineære tidsalgoritmer for lineær programmering og observasjonen av at de samme algoritmene i mange tilfeller kan brukes til å løse geometriske optimaliseringsproblemer som ikke var lineære programmer, går i det minste tilbake til Megiddo ( 1983 , 1984 ), som ga en lineær forventet tid algoritme for både tre-variable lineære programmer og det minste sirkelproblemet. Imidlertid formulerte Megiddo generalisering av lineær programmering geometrisk snarere enn kombinatorisk, som et konvekst optimaliseringsproblem i stedet for som et abstrakt problem på settsystemer. På samme måte observerte Dyer (1986) og Clarkson (i konferanseversjonen fra 1988 av Clarkson 1995 ) at metodene deres kunne brukes på konvekse programmer så vel som lineære programmer. Dyer (1992) viste at det minste omsluttende ellipsoidproblemet også kan formuleres som et konvekst optimaliseringsproblem ved å legge til et lite antall ikke-lineære begrensninger. Bruken av randomisering for å forbedre tidsgrensene for lavdimensjonal lineær programmering og relaterte problemer ble banebrytende av Clarkson og av Dyer & Frieze (1989) .

Definisjonen av problemer av LP-type når det gjelder funksjoner som tilfredsstiller aksiomene lokalitet og monotonicitet er fra Sharir & Welzl (1992) , men andre forfattere i samme tidsramme formulerte alternative kombinatoriske generaliseringer av lineære programmer. For eksempel, i en ramme som er utviklet av Gärtner (1995) , er funksjonen $f$ er erstattet med en total bestilling på undergrupper av $S$ . Det er mulig å bryte båndene i et LP-problem for å skape en total ordre, men bare på bekostning av en økning i den kombinatoriske dimensjonen. I tillegg, som i problemer med LP-typen, definerer Gärtner visse primitiver for å utføre beregninger på undersett av elementer; hans formalisering har imidlertid ikke en analog av den kombinatoriske dimensjonen.

En annen abstrakt generalisering av både lineære programmer og lineære komplementaritetsproblemer , formulert av Stickney & Watson (1978) og senere studert av flere andre forfattere, angår orienteringer av kantene på en hyperkube med egenskapen som hvert ansikt på hyperkuben (inkludert hele hyperkuben) som ansikt) har en unik vask , et toppunkt uten utgående kanter. En orientering av denne typen kan dannes av et problem av LP-type ved å korrespondere undersettene til S med toppunktene i en hyperkube på en slik måte at to delmengder avviker med et enkelt element hvis og bare hvis de tilsvarende hjørnene er tilstøtende, og med orientere kanten mellom $nabosettene$ $A \subseteq B$ mot $B$ hvis $f (A) \neq f (B)$ og mot $A$ ellers. Den resulterende orienteringen har den ekstra egenskapen at den danner en rettet asyklisk graf , hvorfra det kan vises at en randomisert algoritme kan finne den unike synken til hele hyperkuben (det optimale grunnlaget for LP-type problem) i en rekke trinn eksponentiell i kvadratroten til $n$ .

Det mer nylig utviklede rammeverket for krenkerrom generaliserer problemer av LP-typen, i den forstand at hvert problem av LP-type kan modelleres av et krenkelsesrom, men ikke nødvendigvis omvendt. Overtredelsesrom er definert på samme måte som problemer av LP-type, av en funksjon $f$ som tilordner sett til objektive funksjonsverdier, men verdiene til $f$ er ikke ordnet. Til tross for mangel på bestilling, har hvert sett $S$ et veldefinert sett med baser (de minimale settene med samme verdi som hele settet) som kan finnes ved variasjoner av Clarksons algoritmer for problemer med LP-type. Det er faktisk vist at overtredelsesrom nøyaktig karakteriserer systemene som kan løses med Clarksons algoritmer.

Merknader

Referanser

Amenta, Nina (1994), "Helly-type teoremer og generalisert lineær programmering" (PDF) , Discrete and Computational Geometry , 12 (3): 241–261, doi : 10.1007/BF02574379 , MR 1298910 , S2CID 26667725.
Amenta, Nina ; Bern, Marshall; Eppstein, David (1999), "Optimal punktplassering for maskeutjevning ", 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), "Et teorem om heltallgitteret" (PDF) , Studies in Applied Mathematics , 56 (2): 187–188, doi : 10.1002/sapm1977562187 , MR 0462617.
Braß, Peter; Heinrich-Litan, Laura; Morin, Pat (2003), "Computing the center of area of a convex polygon" (PDF) , International Journal of Computational Geometry & Applications , 13 (5): 439–445, doi : 10.1142/S021819590300127X , MR 2012837.
Brise, Yves; Gärtner, Bernd (2011), "Clarksons algoritme for krenkerrom" (PDF) , Computational Geometry: Theory and Applications , 44 (2): 70–81, arXiv : 0906.4706 , doi : 10.1016/j.comgeo.2010.09.003 , MR 2737285 , S2CID 1233875.
Chan, Timothy M. (2004), "En optimal randomisert algoritme for maksimal Tukey -dybde" (PDF) , Proc. 15. ACM-SIAM Symp. Diskrete algoritmer , s. 423–429.
Chazelle, Bernard ; Matoušek, Jiří (1996), "On linear-time deterministic algorithms for optimization problems in fixed dimension" (PDF) , Journal of Algorithms , 21 (3): 579–597, doi : 10.1006/jagm.1996.0060 , MR 1417665 , S2CID 2482481.
Clarkson, Kenneth L. (1995), "Las Vegas -algoritmer for lineær og heltalls programmering når dimensjonen er liten" (PDF) , Journal of the ACM , 42 (2): 488–499, doi : 10.1145/201019.201036 , MR 1409744 , S2CID 6953625.
Dyer, Martin E. (1986), "On a multidimensional search technique and its application to the Euclidean one-center problem", SIAM Journal on Computing , 15 (3): 725–738, doi : 10.1137/0215052 , MR 0850419.
Dyer, Martin E. (1992), "En klasse med konvekse programmer med applikasjoner til beregningsgeometri", Proc. 8. Symposium on Computational Geometry (SCG '92) , Berlin, Tyskland, s. 9–15, doi : 10.1145/142675.142681 , ISBN 0-89791-517-8, S2CID 7654513.
Dyer, Martin E .; Frieze, Alan M. (1989), "En randomisert algoritme for fastdimensjonal lineær programmering", Matematisk programmering , (Ser. A), 44 (2): 203–212, doi : 10.1007/BF01587088 , MR 1003560 , S2CID 206800147.
Eppstein, David (2005), "Quasiconvex programmering", i Goodman, Jacob E .; Pach, János ; Welzl, Emo (red.), Combinatorial and Computational Geometry , MSRI Publications, 52 , Cambridge Univ. Press, s. 287–331, arXiv : cs.CG/0412046 , MR 2178325.
Eppstein, David (2006), "Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms", 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), "The small enclosing ball of balls: combinatorial structure and algorithms" (PDF) , International Journal of Computational Geometry & Applications , 14 (4–5): 341–378, doi : 10.1142/S0218195904001500 , MR 2087827.
Gärtner, Bernd (1995), "A subexponential algorithm for abstract optimization problems" (PDF) , SIAM Journal on Computing , 24 (5): 1018–1035, doi : 10.1137/S0097539793250287 , MR 1350756.
Gärtner, Bernd; Matoušek, Jiří ; Rüst, L .; Škovroň, P. (2008), "Violator spaces: structure and algorithms", Discrete Applied Mathematics , 156 (11): 2124–2141, arXiv : cs.DM/0606087 , doi : 10.1016/j.dam.2007.08.048 , MR 2437006.
Gärtner, Bernd; Welzl, Emo (2001), "A simple sampling lemma: analysis and applications in geometric optimization" (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), "Raske algoritmer for problemer med kollisjon og nærhet som involverer bevegelige geometriske objekter", Computational Geometry. Teori og applikasjoner , 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), "Enkle stokastiske spill, paritetsspill, gjennomsnittlige gevinstspill og rabatterte utbetalingsspill er alle problemer av LP-type" , Algorithmica , 49 (1): 37–50, doi : 10.1007/s00453-007-0175 -3 , MR 2344393 , S2CID 8183965.
Kalai, Gil (1992), "A subexponential randomized simplex algoritme", Proc. 24th ACM Symposium on Theory of Computing , s. 475–482, doi : 10.1145/129712.129759 , S2CID 17447465.
Li, Hongdong (2007), "En praktisk algoritme for $L \infty$ triangulering med ekstremer", Proc. IEEE konf. 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), "Største avgrensningsboks, minste diameter og relaterte problemer på upresise punkter" (PDF) , Computational Geometry Theory and Applications , 43 (4): 419–433, doi : 10.1016/j.comgeo. 2009.03.007 , MR 2575803.
Matoušek, Jiří (1995), "Om geometrisk optimalisering med få krenkede begrensninger", Diskret og beregningsgeometri , 14 (4): 365–384, doi : 10.1007/BF02570713 , MR 1360943.
Matoušek, Jiří (2009), "Fjerne degenerasjon ved problemer med LP-type revidert", Diskret og beregningsgeometri , 42 (4): 517–526, doi : 10.1007/s00454-008-9085-7 , MR 2556452.
Matoušek, Jiří ; Sharir, Micha ; Welzl, Emo (1996), "A subexponential bound for linear programming" (PDF) , Algorithmica , 16 (4–5): 498–516, doi : 10.1007/BF01940877 , S2CID 877032.
Megiddo, Nimrod (1983), "Lineær-tid algoritmer for lineær programmering i $R 3$ og relaterte problemer", SIAM Journal on Computing , 12 (4): 759–776, doi : 10.1137/0212052 , MR 0721011 , S2CID 14467740.
Megiddo, Nimrod (1984), "Lineær programmering i lineær tid når dimensjonen er fikset", Journal of the ACM , 31 (1): 114–127, doi : 10.1145/2422.322418 , MR 0821388 , S2CID 12686747.
Nielsen, Frank; Nock, Richard (2008), "On the small enclosing information disk" (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), "On the planar piecewise quadratic 1-center problem", Algorithmica , 57 (2): 252–283, doi : 10.1007/s00453-008-9210-2 , MR 2587554 , S2CID 18587944.
Scarf, Herbert E. (1977), "En observasjon om produksjonsstrukturen med udelbarheter", 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), " Smådimensjonal lineær programmering og konvekse skrog gjort enkelt", Diskret og beregningsgeometri , 6 (5): 423–434, doi : 10.1007/BF02574699 , MR 1115100.
Sharir, Micha ; Welzl, Emo (1992), "A combinatorial bounded for linear programming and related problems", 9. årlige symposium om teoretiske aspekter av informatikk (STACS), Cachan, Frankrike, 13. – 15. Februar 1992, Proceedings , Lecture Notes in Computer Science , 577 , Springer-Verlag, s. 567–579, doi : 10.1007/3-540-55210-3_213.
Stickney, Alan; Watson, Layne (1978), "Digraph-modeller av algoritmer av Bard-type for det lineære komplementaritetsproblemet", Mathematics of Operations Research , 3 (4): 322–333, doi : 10.1287/moor.3.4.322 , MR 0509668.
Szabó, Tibor; Welzl, Emo (2001), "Unique sink orientations of cubes" (PDF) , 42nd 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), "Smallest enclosing disks (balls and ellipsoids)", i Maurer, H. (red.), New Results and New Trends in Computer Science (PDF) , Lecture Notes in Computer Science (555 utg.) , Springer-Verlag, s. 359–370, doi : 10.1007/BFb0038202.

Languages

In other projects