Problema de tipo LP

En el estudio de algoritmos , un problema de tipo LP (también llamado programa lineal generalizado ) es un problema de optimización que comparte ciertas propiedades con los programas lineales de baja dimensión y que puede resolverse mediante algoritmos similares. Los problemas de tipo LP incluyen muchos problemas de optimización importantes que no son programas lineales en sí mismos, como el problema de encontrar el círculo más pequeño que contiene un conjunto dado de puntos en un plano. Estos problemas pueden resolverse mediante una combinación de algoritmos aleatorios en un tiempo lineal con respecto al número de elementos que definen el problema y subexponencial con respecto a su dimensión.

Definición

Los problemas de tipo LP fueron definidos por Sharir y Welzl (1992) como problemas en los que se proporciona como entrada un conjunto finito $S$ de elementos y una función $f$ que asigna subconjuntos de $S$ a valores de un conjunto totalmente ordenado. Se requiere que la función satisfaga dos propiedades clave:

Monotonicidad: para cada dos conjuntos $A \subseteq B \subseteq S$ , f ( A ) ≤ f ( B ) ≤ f ( S ).
Localidad: para cada dos conjuntos $A \subseteq B \subseteq S$ y cada elemento $x$ en $S$ , si $f (A) = f (B) = f (A \cup {x})$ , entonces $f (A) = f (B \cup {x})$ .

Una base de un problema de tipo LP es un conjunto $B \subseteq S$ con la propiedad de que cada subconjunto propio de $B$ tiene un valor de $f$ menor que el propio $B$ , y la dimensión (o dimensión combinatoria ) de un problema de tipo LP se define como la cardinalidad máxima de una base.

Se supone que un algoritmo de optimización puede evaluar la función $f$ solo en conjuntos que son bases o que se forman añadiendo un único elemento a una base. Alternativamente, el algoritmo puede restringirse a dos operaciones primitivas: una prueba de violación que determina, para una base $B$ y un elemento $x,$ si $f (B) = f (B \cup {x})$ , y un cálculo de base que (con los mismos datos de entrada) encuentra una base de $B \cup {x$ }. La tarea del algoritmo consiste en evaluar $f (S)$ utilizando únicamente estas evaluaciones restringidas o primitivas.

Ejemplos y aplicaciones

Bolas Lp

Un programa lineal puede definirse mediante un sistema de $d$ variables reales no negativas , sujeto a $n$ restricciones de desigualdad lineal, junto con una función objetivo lineal no negativa que debe minimizarse. Esto puede enmarcarse dentro de los problemas de tipo LP al considerar $S$ como el conjunto de restricciones y definir $f (A)$ (para un subconjunto $A$ de las restricciones) como el valor mínimo de la función objetivo del programa lineal más pequeño definido por $A.$ Con supuestos de posición general adecuados (para evitar que múltiples puntos de solución tengan el mismo valor óptimo de la función objetivo), esto satisface los requisitos de monotonicidad y localidad de un problema de tipo LP, y tiene una dimensión combinatoria igual al número $d$ de variables. ^{[ 1 ]} De manera similar, un programa entero (que consiste en un conjunto de restricciones lineales y una función objetivo lineal, como en un programa lineal, pero con la restricción adicional de que las variables deben tomar solo valores enteros) satisface tanto las propiedades de monotonicidad como de localidad de un problema de tipo LP, con los mismos supuestos de posición general que para los programas lineales. Los teoremas de Bell (1977) y Scarf (1977) muestran que, para un programa entero con $d$ variables, la dimensión combinatoria es como máximo $2$ $d$ . ^[¹^]

Muchos problemas de optimización naturales en geometría computacional son de tipo LP:

El problema del círculo más pequeño consiste en encontrar el radio mínimo de un círculo que contiene un conjunto dado de $n$ puntos en el plano. Satisface la monotonicidad (añadir más puntos solo puede hacer que el círculo sea más grande) y la localidad (si el círculo más pequeño para el conjunto $A$ contiene $B$ y $x$ , entonces el mismo círculo también contiene $B \cup {x$ }). Debido a que el círculo más pequeño siempre está determinado por algunos tres puntos, el problema del círculo más pequeño tiene dimensión combinatoria tres, aunque se define utilizando geometría euclidiana bidimensional. ^{[ 2 ]} De manera más general, la bola de puntos más pequeña que encierra en $d$ dimensiones forma un problema de tipo LP de dimensión combinatoria $d + 1$ . El problema del círculo más pequeño se puede generalizar a la bola más pequeña que encierra un conjunto de bolas, ^{[ 3 ]} a la bola más pequeña que toca o rodea a cada una de las bolas de un conjunto, ^{[ 4 ]} al problema del 1-centro ponderado , ^{[ 5 ]} o a problemas similares de bolas envolventes más pequeñas en espacios no euclidianos como el espacio con distancias definidas por la divergencia de Bregman . ^{[ 6 ]} El problema relacionado de encontrar el elipsoide envolvente más pequeño también es un problema de tipo LP, pero con una dimensión combinatoria mayor, $d (d +3)/2$ . ^{[ 7 ]}
Sea $K 0, K 1, ...$ una sucesión de $n$ conjuntos convexos en un espacio euclidiano $d$ -dimensional, y supongamos que deseamos encontrar el prefijo más largo de esta sucesión que tenga un punto de intersección común. Esto puede expresarse como un problema de tipo LP en el que $f (A) = - i$ donde K _i es el primer miembro de A que no pertenece a un prefijo de intersección de A , y donde $f (A) = - n$ si no existe tal miembro. La dimensión combinatoria de este sistema es $d + 1$ . ^{[ 8 ]}
Supongamos que tenemos una colección de cajas rectangulares alineadas con los ejes en un espacio tridimensional y deseamos encontrar una línea dirigida hacia el octante positivo del espacio que corte todas las cajas. Esto puede expresarse como un problema de tipo LP con dimensión combinatoria 4. ^{[ 9 ]}
El problema de hallar la distancia mínima entre dos politopos convexos , especificados por sus conjuntos de vértices, puede representarse como un problema de tipo LP. En esta formulación, el conjunto $S$ es el conjunto de todos los vértices de ambos politopos, y el valor de la función $f (A)$ es la negación de la distancia mínima entre las envolventes convexas de los dos subconjuntos $A$ de vértices de los dos politopos. La dimensión combinatoria del problema es $d + 1$ si los dos politopos son disjuntos, o $d + 2$ si tienen una intersección no vacía. ^{[ 1 ]}
Sea $S = {f 0, f 1, ...$ } un conjunto de funciones cuasiconvexas . Entonces, el máximo puntual $max i f i$ es también cuasiconvexo, y el problema de encontrar el valor mínimo de $max i f i$ es un problema de tipo LP. Tiene una dimensión combinatoria de como máximo $2 d + 1$ , donde $d$ es la dimensión del dominio de las funciones, pero para funciones suficientemente suaves la dimensión combinatoria es menor, como máximo $d + 1$ . Muchos otros problemas de tipo LP también pueden expresarse utilizando funciones cuasiconvexas de esta manera; por ejemplo, el problema del círculo más pequeño que encierra es el problema de minimizar $max i f i$ donde cada una de las funciones $f i$ mide la distancia euclidiana desde uno de los puntos dados. ^{[ 10 ]}

Los problemas de tipo LP también se han utilizado para determinar los resultados óptimos de ciertos juegos en la teoría de juegos algorítmica , ^{[ 11 ]} mejorar la colocación de vértices en mallas del método de elementos finitos , ^{[ 12 ]} resolver problemas de localización de instalaciones , ^{[ 13 ]} analizar la complejidad temporal de ciertos algoritmos de búsqueda de tiempo exponencial, ^{[ 14 ]} y reconstruir las posiciones tridimensionales de objetos a partir de sus imágenes bidimensionales. ^{[ 15 ]}

Algoritmos

Seidel

Seidel (1991) propuso un algoritmo para programación lineal de baja dimensión que puede adaptarse al marco de problemas de tipo LP. El algoritmo de Seidel toma como entrada el conjunto $S$ y un conjunto separado $X$ (inicialmente vacío) de elementos que se sabe que pertenecen a la base óptima. Luego, considera los elementos restantes uno por uno en un orden aleatorio, realizando pruebas de violación para cada uno y, según el resultado, llamando recursivamente al mismo algoritmo con un conjunto mayor de elementos de la base conocidos. Puede expresarse con el siguiente pseudocódigo :

función seidel( S , f , X ) es R := conjunto vacío B := X para x en una permutación aleatoria de S : si f ( B ) ≠ f ( B ∪ { x }): B := seidel( R , f , X ∪ { x }) R := R ∪ { x } retornar B

En un problema con dimensión combinatoria $d$ , la prueba de violación en la $i$ -ésima iteración del algoritmo falla solo cuando $x$ es uno de los $d - | X |$ elementos base restantes, lo que ocurre con una probabilidad como máximo $(d - | X |)/ i$ . Basándonos en este cálculo, se puede demostrar que, en general, el número esperado de pruebas de violación realizadas por el algoritmo es $O(d! n)$ , lineal en $n$ pero peor que exponencial en $d$ .

Clarkson

Clarkson (1995) define dos algoritmos, uno recursivo y otro iterativo, para la programación lineal basada en técnicas de muestreo aleatorio, y sugiere una combinación de ambos que llama al algoritmo iterativo desde el algoritmo recursivo. El algoritmo recursivo elige repetidamente muestras aleatorias cuyo tamaño es aproximadamente la raíz cuadrada del tamaño de entrada, resuelve el problema muestreado de forma recursiva y luego utiliza pruebas de violación para encontrar un subconjunto de los elementos restantes que debe incluir al menos un elemento base.

función recursiva( S , f ) es X := conjunto vacío repetir R := un subconjunto aleatorio de S de tamaño d√n B := base para R ∪ X , calculada recursivamente V := { x | f ( B ) ≠ f ( B ∪ { x })} X := X ∪ V hasta que V esté vacío devolver B

En cada iteración, el tamaño esperado de $V$ es $O(\sqrt n)$ , ^{[ 16 ]} y siempre que $V$ no esté vacío incluye al menos un nuevo elemento de la base eventual de $S$ . Por lo tanto, el algoritmo realiza como máximo $d$ iteraciones, cada una de las cuales realiza $n$ pruebas de violación y hace una única llamada recursiva a un subproblema de tamaño $O(d \sqrt n)$ .

El algoritmo iterativo de Clarkson asigna pesos a cada elemento de $S$ , inicialmente todos iguales. Luego elige aleatoriamente un conjunto $R$ de $9d²$ elementos de $S y calcula los conjuntos$ $B$ y $V$ como en el algoritmo anterior. Si el peso total de $V$ es como máximo $2/(9d - 1)$ veces el peso total de $S$ $($ $como$ ocurre con probabilidad constante), el algoritmo duplica los pesos de cada elemento de $V$ y, como antes, repite este proceso hasta que $V$ quede vacío. En cada iteración, se puede demostrar que el peso de la base óptima aumenta a un ritmo mayor que el peso total de $S$ , de lo cual se deduce que el algoritmo debe terminar en $O(log n)$ iteraciones.

Al usar el algoritmo recursivo para resolver un problema dado, cambiar al algoritmo iterativo para sus llamadas recursivas y luego cambiar nuevamente al algoritmo de Seidel para las llamadas realizadas por el algoritmo iterativo, es posible resolver un problema de tipo LP dado usando $O(dn + d! d O(1) log n)$ pruebas de violación.

Cuando se aplica a un programa lineal, este algoritmo puede interpretarse como un método simplex dual . ^{[ 17 ]} Con ciertas primitivas computacionales adicionales más allá de las primitivas de prueba de violación y cálculo de base, este método puede hacerse determinista. ^{[ 18 ]}

Matoušek, Sharir y Welzl

Matoušek, Sharir y Welzl (1996) describen un algoritmo que utiliza una propiedad adicional de los programas lineales que no siempre se cumple en otros problemas de tipo LP, que todas las bases tienen la misma cardinalidad entre sí. Si un problema de tipo LP no tiene esta propiedad, se le puede hacer que la tenga agregando $d$ nuevos elementos ficticios y modificando la función $f$ para que devuelva el par ordenado de su antiguo valor $f (A)$ y del número $min(d,| A |)$ , ordenado lexicográficamente .

En lugar de agregar elementos de S uno por uno, o encontrar muestras de los elementos, Matoušek, Sharir y Welzl (1996) describen un algoritmo que elimina elementos uno por uno. En cada paso, mantiene una base $C$ que inicialmente puede ser el conjunto de elementos ficticios. Se puede describir con el siguiente pseudocódigo:

La función msw( S , f , C ) es si S = C entonces devuelve C elige un elemento aleatorio x de S \ C B = msw( S \ x , f , C ) si f ( B ) ≠ f(B ∪ {x}) entonces B := basis( B ∪ { x }) B := msw( S , f , B ) devuelve B

En la mayoría de las llamadas recursivas del algoritmo, la prueba de violación tiene éxito y se omite la instrucción if. Sin embargo, con una pequeña probabilidad, la prueba de violación falla y el algoritmo realiza un cálculo de base adicional y luego una llamada recursiva adicional. Como muestran los autores, el tiempo esperado para el algoritmo es lineal en n y exponencial en la raíz cuadrada de $d log n$ . Al combinar este método con los procedimientos recursivos e iterativos de Clarkson, estas dos formas de dependencia temporal pueden separarse, lo que resulta en un algoritmo que realiza O( dn ) pruebas de violación en el algoritmo recursivo externo y un número que es exponencial en la raíz cuadrada de $d log d$ en los niveles inferiores del algoritmo. ^{[ 19 ]}

Variaciones

Optimización con valores atípicos

Matoušek (1995) considera una variación de los problemas de optimización de tipo LP en la que se da, junto con el conjunto $S$ y la función objetivo $f$ , un número $k$ ; la tarea es eliminar $k$ elementos de $S$ para que la función objetivo en el conjunto restante sea lo más pequeña posible. Por ejemplo, cuando se aplica al problema del círculo más pequeño, esto daría el círculo más pequeño que contiene todos menos $k$ de un conjunto dado de puntos planares. Muestra que, para todos los problemas de tipo LP no degenerados (es decir, problemas en los que todas las bases tienen valores distintos) este problema puede resolverse en tiempo $O($ nk $d$ $)$ $,$ resolviendo un conjunto de $O(k d)$ problemas de tipo LP definidos por subconjuntos de $S.$

Problemas implícitos

Algunos problemas de optimización geométrica pueden expresarse como problemas de tipo LP en los que el número de elementos en la formulación de tipo LP es significativamente mayor que el número de valores de datos de entrada para el problema de optimización. Como ejemplo, consideremos un conjunto de $n$ puntos en el plano, cada uno moviéndose con velocidad constante. En cualquier instante, el diámetro de este sistema es la distancia máxima entre dos de sus puntos. El problema de encontrar un instante en el que el diámetro se minimice puede formularse como la minimización del máximo puntual de $O(n²) funciones$ cuasiconvexas, una para cada par de puntos, que miden la distancia euclidiana entre el par en función del tiempo. Por lo tanto, puede resolverse como un problema de tipo LP de dimensión combinatoria dos sobre un conjunto de $O(n²)$ elementos, pero este conjunto es significativamente mayor que el número de puntos de entrada $.$ ^{[ 20 ]}

Chan (2004) describe un algoritmo para resolver problemas de tipo LP definidos implícitamente como este, en el que cada elemento de tipo LP está determinado por una $k$ -tupla de valores de entrada, para alguna constante $k$ . Para aplicar su enfoque, debe existir un algoritmo de decisión que pueda determinar, para una base de tipo LP dada $B$ y un conjunto $S$ de $n$ valores de entrada, si $B$ es una base para el problema de tipo LP determinado por $S.$

El algoritmo de Chan realiza los siguientes pasos:

Si el número de valores de entrada es inferior a un cierto valor umbral, encuentre el conjunto de elementos de tipo LP que determina y resuelva el problema explícito de tipo LP resultante.
De lo contrario, divida los valores de entrada en un número adecuado mayor que $k$ de subconjuntos de igual tamaño $S i$ .
Si $f$ es la función objetivo del problema de programación lineal (PL) implícitamente definido que se va a resolver, entonces definamos una función $g$ que mapee conjuntos de subconjuntos $S i$ al valor de $f$ en la unión de dichos conjuntos. Entonces, el conjunto de subconjuntos $S i$ y la función objetivo $g$ definen un problema de PL de la misma dimensión que el problema implícito que se va a resolver.
Resuelva el problema de programación lineal (explícito) definido por $g$ utilizando el algoritmo de Clarkson, que realiza un número lineal de pruebas de violación y un número polilogarítmico de evaluaciones de base. Las evaluaciones de base para $g$ pueden realizarse mediante llamadas recursivas al algoritmo de Chan, y las pruebas de violación pueden realizarse mediante llamadas al algoritmo de decisión.

Con la suposición de que el algoritmo de decisión toma una cantidad de tiempo $O(T (n))$ que crece al menos polinomialmente como una función del tamaño de entrada $n$ , Chan muestra que el umbral para cambiar a una formulación LP explícita y el número de subconjuntos en la partición se pueden elegir de tal manera que el algoritmo de optimización de tipo LP implícito también se ejecute en un tiempo $O(T (n))$ .

Por ejemplo, para el diámetro mínimo de puntos móviles, el algoritmo de decisión solo necesita calcular el diámetro de un conjunto de puntos en un tiempo fijo, un problema que se puede resolver en tiempo $O(n log n)$ utilizando la técnica de los calibradores giratorios . Por lo tanto, el algoritmo de Chan para encontrar el tiempo en el que se minimiza el diámetro también toma un tiempo $O(n log n)$ . Chan utiliza este método para encontrar un punto de máxima profundidad de Tukey entre una colección dada de $n$ puntos en un espacio euclidiano $d-$ dimensional, en un tiempo $O(n d - 1 + n log n)$ . Una técnica similar fue utilizada por Braß, Heinrich-Litan y Morin (2003) para encontrar un punto de máxima profundidad de Tukey para la distribución uniforme en un polígono convexo.

Historia y problemas relacionados

El descubrimiento de algoritmos de tiempo lineal para la programación lineal y la observación de que estos mismos algoritmos podían utilizarse en muchos casos para resolver problemas de optimización geométrica que no eran programas lineales se remonta al menos a Megiddo ( 1983 , 1984 ) , quien proporcionó un algoritmo de tiempo esperado lineal tanto para programas lineales de tres variables como para el problema del círculo más pequeño. Sin embargo, Megiddo formuló la generalización de la programación lineal geométricamente en lugar de combinatoriamente, como un problema de optimización convexa en vez de un problema abstracto sobre sistemas de conjuntos. De manera similar, Dyer (1986) y Clarkson (en la versión de la conferencia de 1988 de Clarkson 1995 ) observaron que sus métodos podían aplicarse tanto a programas convexos como a programas lineales. Dyer (1992) demostró que el problema del elipsoide mínimo envolvente también podía formularse como un problema de optimización convexa añadiendo un pequeño número de restricciones no lineales. El uso de la aleatorización para mejorar los límites de tiempo para la programación lineal de baja dimensión y problemas relacionados fue iniciado por Clarkson y por Dyer y Frieze (1989) .

La definición de problemas de tipo LP en términos de funciones que satisfacen los axiomas de localidad y monotonicidad proviene de Sharir y Welzl (1992) , pero otros autores en el mismo período formularon generalizaciones combinatorias alternativas de programas lineales. Por ejemplo, en un marco desarrollado por Gärtner (1995) , la función $f$ se reemplaza por un orden total en los subconjuntos de $S.$ Es posible romper los empates en un problema de tipo LP para crear un orden total, pero solo a costa de un aumento en la dimensión combinatoria. ^{[ 21 ]} Además, como en los problemas de tipo LP, Gärtner define ciertas primitivas para realizar cálculos en subconjuntos de elementos; sin embargo, su formalización no tiene un análogo de la dimensión combinatoria.

Otra generalización abstracta de los problemas de programación lineal y de complementariedad lineal , formulada por Stickney y Watson (1978) y posteriormente estudiada por otros autores, se refiere a las orientaciones de las aristas de un hipercubo con la propiedad de que cada cara del hipercubo (incluido el hipercubo completo como cara) tiene un único sumidero , un vértice sin aristas salientes. Una orientación de este tipo puede formarse a partir de un problema de tipo LP haciendo coincidir los subconjuntos de S con los vértices de un hipercubo de tal manera que dos subconjuntos difieran en un solo elemento si y solo si los vértices correspondientes son adyacentes, y orientando la arista entre conjuntos vecinos $A \subseteq B$ hacia $B$ si $f (A) \neq f (B)$ y hacia $A$ en caso contrario. La orientación resultante tiene la propiedad adicional de que forma un grafo dirigido acíclico , a partir del cual se puede demostrar que un algoritmo aleatorio puede encontrar el único sumidero de todo el hipercubo (la base óptima del problema de tipo LP) en un número de pasos exponencial en la raíz cuadrada de $n$ . ^[²²^]

El marco de trabajo más reciente de los espacios de violadores generaliza los problemas de tipo LP, en el sentido de que todo problema de tipo LP puede modelarse mediante un espacio de violadores, pero no necesariamente a la inversa. Los espacios de violadores se definen de forma similar a los problemas de tipo LP, mediante una función $f$ que asigna conjuntos a valores de la función objetivo, pero los valores de $f$ no están ordenados. A pesar de la falta de orden, todo conjunto $S$ tiene un conjunto bien definido de bases (los conjuntos mínimos con el mismo valor que el conjunto completo) que pueden hallarse mediante variaciones de los algoritmos de Clarkson para problemas de tipo LP. De hecho, se ha demostrado que los espacios de violadores caracterizan con precisión los sistemas que pueden resolverse mediante los algoritmos de Clarkson. ^{[ 23 ]}

Notas

^ Matoušek , Sharir y Welzl (1996 ) .
↑ Aunque el problema del círculo más pequeño fue planteado por primera vez como un problema de tipo LP por Matoušek, Sharir y Welzl (1996) , varios artículos anteriores describieron algoritmos para este problema basados en ideas de programación lineal de baja dimensión, incluidos Megiddo (1983) y Welzl (1991) .
↑ Fischer y Gärtner (2004) .
↑ Löffler y van Kreveld (2010) .
↑ Dyer (1986) .
↑ Nielsen y Nock (2008) .
^ Matoušek, Sharir y Welzl (1996) ; Welzl (1991) .
↑ Chan (2004) .
↑ Amenta (1994) .
^ Amenta, Berna y Eppstein (1999) ; Eppstein (2005) .
↑ Halman (2007) .
↑ Amenta, Berna y Eppstein (1999) .
↑ Puerto, Rodríguez-Chía & Tamir (2010) .
↑ Eppstein (2006) .
↑ Li (2007) .
↑ También se conocenlímites de cola para el tamaño de $V : véase$ Gärtner y Welzl (2001) .
↑ Kalai (1992) .
↑ Chazelle y Matoušek (1996) .
↑ Matoušek, Sharir y Welzl (1996) . Kalai (1992) también dio un límite de tiempo muy similar para la programación lineal.
↑ La formulación de tipo LP de este problema fue dada por Chan (2004) , pero ya había sido estudiada utilizando otros métodos algorítmicos por Gupta, Janardan y Smid (1996) . Chan también cita un manuscrito inédito de Clarkson para un $algoritmo de tiempo O(n log n)$ , que coincide con el tiempo que se puede lograr con el enfoque implícito de tipo LP.
↑ Matoušek (2009) .
↑ Szabó y Welzl (2001) .
↑ Gartner y col. (2008) ; Brise y Gärtner (2011) .

Referencias

Amenta, Nina (1994), "Teoremas de tipo Helly y programación lineal generalizada" (PDF) , Geometría discreta y computacional , 12 (3): 241–261 , doi : 10.1007/BF02574379 , MR 1298910 , S2CID 26667725 .
Amenta, Nina ; Bern, Marshall; Eppstein, David (1999), "Posición óptima de puntos para suavizado de mallas", 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), "Un teorema sobre la red entera" (PDF) , Studies in Applied Mathematics , 56 (2): 187–188 , doi : 10.1002/sapm1977562187 , MR 0462617 .
Braß, Peter; Heinrich-Litan, Laura; Morin, Pat (2003), "Cálculo del centro de área de un polígono convexo" (PDF) , International Journal of Computational Geometry & Applications , 13 (5): 439–445 , doi : 10.1142/S021819590300127X , MR 2012837 .
Brise, Yves; Gärtner, Bernd (2011), "Algoritmo de Clarkson para espacios violadores" (PDF) , Geometría Computacional: Teoría y Aplicaciones , 44 (2): 70–81 , arXiv : 0906.4706 , doi : 10.1016/j.comgeo.2010.09.003 , MR 2737285 , S2CID 1233875 .
Chan, Timothy M. (2004), "Un algoritmo aleatorio óptimo para la máxima profundidad de Tukey" (PDF) , Actas del 15.º Simposio ACM-SIAM sobre Algoritmos Discretos , págs. 423–429 . .
Chazelle, Bernard ; Matoušek, Jiří (1996), "Sobre algoritmos deterministas de tiempo lineal para problemas de optimización en dimensión fija" (PDF) , Journal of Algorithms , 21 (3): 579–597 , doi : 10.1006/jagm.1996.0060 , MR 1417665 , S2CID 2482481 .
Clarkson, Kenneth L. (1995), "Algoritmos de Las Vegas para programación lineal y entera cuando la dimensión es pequeña" (PDF) , Journal of the ACM , 42 (2): 488–499 , doi : 10.1145/201019.201036 , MR 1409744 , S2CID 6953625 .
Dyer, Martin E. (1986), "Sobre una técnica de búsqueda multidimensional y su aplicación al problema euclidiano de un centro", SIAM Journal on Computing , 15 (3): 725–738 , doi : 10.1137/0215052 , MR 0850419 .
Dyer, Martin E. (1992), "Una clase de programas convexos con aplicaciones a la geometría computacional", Actas del 8.º Simposio sobre Geometría Computacional (SCG '92) , Berlín, Alemania, pp. 9–15 , doi : 10.1145/142675.142681 , ISBN 0-89791-517-8, S2CID 7654513 {{citation}}: CS1 mantenimiento: falta el editor de ubicación ( enlace ) .
Dyer, Martin E.; Frieze, Alan M. (1989), "Un algoritmo aleatorio para programación lineal de dimensión fija", Mathematical Programming , (Ser. A), 44 (2): 203– 212, doi : 10.1007/BF01587088 , MR 1003560 , S2CID 206800147 .
Eppstein, David (2005), "Programación cuasiconvexa", en Goodman, Jacob E.; Pach, János ; Welzl, Emo (eds.), Geometría combinatoria y computacional , MSRI Publications, vol. 52, Cambridge Univ. Press, pp. 287–331 , arXiv : cs.CG/0412046 , MR 2178325 .
Eppstein, David (2006), "Análisis cuasiconvexo de ecuaciones de recurrencia multivariadas para algoritmos de retroceso", 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), "La bola de bolas envolvente más pequeña: estructura combinatoria y algoritmos" (PDF) , International Journal of Computational Geometry & Applications , 14 ( 4–5 ): 341–378 , doi : 10.1142/S0218195904001500 , MR 2087827 .
Gärtner, Bernd (1995), "Un algoritmo subexponencial para problemas de optimización abstractos" (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), "Espacios infractores: estructura y algoritmos", Matemáticas aplicadas discretas , 156 (11): 2124– 2141, arXiv : cs.DM/0606087 , doi : 10.1016/j.dam.2007.08.048 , MR 2437006 .
Gärtner, Bernd; Welzl, Emo (2001), "Un lema de muestreo simple: análisis y aplicaciones en optimización geométrica" (PDF) , Geometría discreta y computacional , 25 (4): 569–590 , doi : 10.1007/s00454-001-0006-2 , MR 1838420 , S2CID 14263014 .
Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1996), "Algoritmos rápidos para problemas de colisión y proximidad que involucran objetos geométricos en movimiento", Geometría Computacional. Teoría y Aplicaciones , 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), "Los juegos estocásticos simples, los juegos de paridad, los juegos de pago medio y los juegos de pago descontado son todos problemas de tipo LP" , Algorithmica , 49 (1): 37–50 , doi : 10.1007/s00453-007-0175-3 , MR 2344393 , S2CID 8183965 .
Kalai, Gil (1992), "Un algoritmo simplex aleatorio subexponencial", Actas del 24.º Simposio ACM sobre Teoría de la Computación , págs. 475–482 , doi : 10.1145/129712.129759 , S2CID 17447465 .
Li, Hongdong (2007), "Un algoritmo práctico para la triangulación $L \infty$ con valores atípicos", Actas de la Conferencia IEEE sobre Visión por Computadora y Reconocimiento de Patrones (CVPR '07) , págs. 1–8 , doi : 10.1109/CVPR.2007.383068 , hdl : 1885/39190 , ISBN 978-1-4244-1179-5, S2CID 14882916 .
Löffler, Maarten; van Kreveld, Marc (2010), "Largest bounding box, smallest diameter, and related problems on imprecise points" (PDF) , Computational Geometry Theory and Applications , 43 (4): 419–433 , doi : 10.1016/j.comgeo.2009.03.007 , MR 2575803 .
Matoušek, Jiří (1995), "Sobre la optimización geométrica con pocas restricciones violadas", Geometría discreta y computacional , 14 (4): 365– 384, doi : 10.1007/BF02570713 , MR 1360943 .
Matoušek, Jiří (2009), "Revisando la eliminación de la degeneración en problemas de tipo LP", Geometría discreta y computacional , 42 (4): 517– 526, doi : 10.1007/s00454-008-9085-7 , hdl : 20.500.11850/156948 , MR 2556452 .
Matoušek, Jiří ; Sharir, Micha ; Welzl, Emo (1996), "Un límite subexponencial para la programación lineal" (PDF) , Algorithmica , 16 ( 4– 5): 498– 516, doi : 10.1007/BF01940877 , S2CID 877032 .
Megiddo, Nimrod (1983), "Algoritmos de tiempo lineal para programación lineal en $R 3$ y problemas relacionados", SIAM Journal on Computing , 12 (4): 759– 776, doi : 10.1137/0212052 , MR 0721011 , S2CID 14467740 .
Megiddo, Nimrod (1984), "Programación lineal en tiempo lineal con dimensión fija", Journal of the ACM , 31 (1): 114– 127, doi : 10.1145/2422.322418 , MR 0821388 , S2CID 12686747 .
Nielsen, Frank; Nock, Richard (2008), "Sobre el disco de información de contención más pequeño" (PDF) , Information Processing Letters , 105 (3): 93–97 , doi : 10.1016/j.ipl.2007.08.007 , MR 2378119 , S2CID 7570507 .
Puerto, J.; Rodríguez-Chía, AM; Tamir, A. (2010), "Sobre el problema cuadrático por partes planar de 1 centro", Algorithmica , 57 (2): 252– 283, doi : 10.1007/s00453-008-9210-2 , MR 2587554 , S2CID 18587944 .
Scarf, Herbert E. (1977), "Una observación sobre la estructura de los conjuntos de producción con indivisibilidades", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 74 (9): 3637– 3641, Bibcode : 1977PNAS...74.3637S , doi : 10.1073/pnas.74.9.3637 , MR 0452678 , PMC 431672 , PMID 16592435 .
Seidel, Raimund (1991), "Programación lineal de pequeña dimensión y envolventes convexas simplificadas", Geometría discreta y computacional , 6 (5): 423– 434, doi : 10.1007/BF02574699 , MR 1115100 .
Sharir, Micha ; Welzl, Emo (1992), "Una cota combinatoria para la programación lineal y problemas relacionados", Stacs 92 , Lecture Notes in Computer Science, vol. 577, Springer-Verlag, pp. 567–579 , doi : 10.1007/3-540-55210-3_213 , ISBN 978-3-540-55210-9.
Stickney, Alan; Watson, Layne (1978), "Modelos de digrafos de algoritmos de tipo Bard para el problema de complementariedad lineal", Mathematics of Operations Research , 3 (4): 322–333 , doi : 10.1287/moor.3.4.322 , MR 0509668 .
Szabó, Tibor; Welzl, Emo (2001), "Orientaciones únicas de sumidero de cubos" (PDF) , 42.º Simposio IEEE sobre Fundamentos de la Informática (Las Vegas, NV, 2001) , pp. 547–555 , doi : 10.1109/SFCS.2001.959931 , ISBN 0-7695-1390-5, MR 1948744 , S2CID 6597643 .
Welzl, Emo (1991), "Discos envolventes más pequeños (bolas y elipsoides)", en Maurer, H. (ed.), Nuevos resultados y nuevas tendencias en informática (PDF) , Lecture Notes in Computer Science, vol. 555 ( ed. 555), Springer-Verlag, pp. 359–370 , doi : 10.1007/BFb0038202 , ISBN 3-540-54869-6.

[msw96-1] Matoušek , Sharir y Welzl (1996 ) .

[2] Aunque el problema del círculo más pequeño fue planteado por primera vez como un problema de tipo LP por Matoušek, Sharir y Welzl (1996) , varios artículos anteriores describieron algoritmos para este problema basados en ideas de programación lineal de baja dimensión, incluidos Megiddo (1983) y Welzl (1991) .

[3] Fischer y Gärtner (2004) .

[4] Löffler y van Kreveld (2010) .

[5] Dyer (1986) .

[6] Nielsen y Nock (2008) .

[7] Matoušek, Sharir y Welzl (1996) ; Welzl (1991) .

[8] Chan (2004) .

[9] Amenta (1994) .

[10] Amenta, Berna y Eppstein (1999) ; Eppstein (2005) .

[11] Halman (2007) .

[12] Amenta, Berna y Eppstein (1999) .

[13] Puerto, Rodríguez-Chía & Tamir (2010) .

[14] Eppstein (2006) .

[15] Li (2007) .

[16] También se conocenlímites de cola para el tamaño de $V : véase$ Gärtner y Welzl (2001) .

[17] Kalai (1992) .

[18] Chazelle y Matoušek (1996) .

[19] Matoušek, Sharir y Welzl (1996) . Kalai (1992) también dio un límite de tiempo muy similar para la programación lineal.

[20] La formulación de tipo LP de este problema fue dada por Chan (2004) , pero ya había sido estudiada utilizando otros métodos algorítmicos por Gupta, Janardan y Smid (1996) . Chan también cita un manuscrito inédito de Clarkson para un $algoritmo de tiempo O(n log n)$ , que coincide con el tiempo que se puede lograr con el enfoque implícito de tipo LP.

[21] Matoušek (2009) .

[22] Szabó y Welzl (2001) .

[23] Gartner y col. (2008) ; Brise y Gärtner (2011) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[

[ 23 ]