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 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 en sí mismos programas lineales, como el problema de encontrar el círculo más pequeño que contiene un conjunto dado de puntos planos. Pueden resolverse mediante una combinación de algoritmos aleatorios en una cantidad de tiempo lineal en el número de elementos que definen el problema y subexponencial en la dimensión del problema.

Los problemas de tipo LP fueron definidos por Sharir y Welzl (1992) como problemas en los que se da como entrada un conjunto finito S de elementos y una función f que mapea subconjuntos de S a valores de un conjunto totalmente ordenado. La función es necesaria para satisfacer dos propiedades clave:

  • Monotonicidad: por cada dos conjuntos A ⊆ B ⊆ S , f ( A ) ≤ f ( B ) ≤ f ( S ).
  • Localidad: para cada dos conjuntos A ⊆ B ⊆ S y cada elemento x en S , si f ( A ) = f ( B ) = f ( A ∪ { x }) , entonces f ( A ) = f ( B ∪ { x }) .

Una base de un problema de tipo LP es un conjunto B ⊆ S con la propiedad de que cada subconjunto propio de B tiene un valor de f más pequeño que el propio B , y la dimensión (o dimensión combinatoria ) de un problema de tipo LP se define como ser 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 en sí mismos bases o que se forman agregando un solo 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 ∪ { x }) , y un cálculo de base que (con la misma entradas) encuentra una base de B ∪ { x }. La tarea que debe realizar el algoritmo es evaluar f ( S ) utilizando únicamente estas primitivas o evaluaciones restringidas.

"> File:Lp Balls.webmReproducir medios
Bolas Lp

Un programa lineal puede definirse mediante un sistema de d variables reales no negativas , sujetas a n restricciones de desigualdad lineal, junto con una función objetivo lineal no negativa a minimizar. Esto se puede colocar en el marco de los problemas de tipo LP dejando que S sea ​​el conjunto de restricciones y definiendo 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 Una . Con supuestos de posición general adecuados (para evitar que múltiples puntos de solución tengan el mismo valor de función objetivo óptimo), 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 consta de una colección 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 . [1]

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

Problema del círculo más pequeño
  • El problema del círculo más pequeño es el problema de encontrar el radio mínimo de un círculo que contiene un conjunto dado de n puntos en el plano. Satisface monotonicidad (añadiendo más puntos sólo pueden hacer que el círculo más grande) y la localidad (si el círculo más pequeño para el grupo A contiene B y x , entonces el mismo círculo contiene también B ∪ { x }). Debido a que el círculo más pequeño siempre está determinado por unos tres puntos, el problema del círculo más pequeño tiene una dimensión combinatoria tres, aunque se define utilizando geometría euclidiana bidimensional. [2] De manera más general, la bola de puntos envolvente más pequeña en dimensiones d 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 cada una de un conjunto de bolas, [4] al problema ponderado de 1 centro , [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 es también un problema de tipo LP, pero con una dimensión combinatoria más grande, d ( d + 3) / 2 . [7]
  • Sea K 0 , K 1 , ... una secuencia de n conjuntos convexos en el espacio euclidiano d- dimensional, y suponga que deseamos encontrar el prefijo más largo de esta secuencia que tiene un punto de intersección común. Esto puede expresarse como un problema de tipo LP en la 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 hay no es tal miembro. La dimensión combinatoria de este sistema es d + 1 . [8]
  • Suponga que se nos da una colección de cajas rectangulares alineadas con el eje en un espacio tridimensional y deseamos encontrar una línea dirigida hacia el octante positivo del espacio que atraviese todas las cajas. Esto puede expresarse como un problema de tipo LP con dimensión combinatoria 4. [9]
  • El problema de encontrar la distancia más cercana 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 en ambos politopos, y el valor de la función f ( A ) es la negación de la distancia más pequeña entre los cascos convexos de los dos subconjuntos A de vértices en los dos politopos. La dimensión combinatoria del problema es d + 1 si los dos politopos son disjuntos, od + 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 en sí mismo cuasiconvexo, y el problema de encontrar el valor mínimo de max i f i es un problema de tipo LP. Tiene dimensión combinatoria 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 se pueden expresar utilizando funciones cuasiconvexas de esta manera; por ejemplo, el problema de círculo circundante más pequeño 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 algorítmica de juegos , [11] mejorar la ubicación de los vértices en mallas de métodos de elementos finitos , [12] resolver problemas de ubicación de instalaciones , [13] analizar la complejidad temporal de ciertas algoritmos de búsqueda en tiempo exponencial, [14] y reconstruyen las posiciones tridimensionales de los objetos a partir de sus imágenes bidimensionales. [15]

Seidel

Seidel (1991) proporcionó un algoritmo para la 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, dependiendo del resultado, realizando una llamada recursiva al mismo algoritmo con un conjunto más grande de elementos básicos conocidos. Puede expresarse con el siguiente pseudocódigo:

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

En un problema con la 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 básicos restantes, lo que ocurre con probabilidad como máximo ( d - | X |) / i . Con base 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, un algoritmo recursivo y un algoritmo iterativo, para la programación lineal basada en técnicas de muestreo aleatorio, y sugiere una combinación de los dos que llama al algoritmo iterativo del 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 usa pruebas de violación para encontrar un subconjunto de los elementos restantes que deben incluir al menos un elemento base:

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

En cada iteración, el tamaño esperado de V es O ( √ n ) , [16] y cuando V es no vacío que 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 realiza una única llamada recursiva a un subproblema de tamaño O ( d √ n ) .

El algoritmo iterativo de Clarkson asigna pesos a cada elemento de S , inicialmente todos ellos iguales. Luego elige un conjunto R de 9 d 2 elementos de S al azar y calcula los conjuntos B y V como en el algoritmo anterior. Si el peso total de V es como mucho 2 / (9 d - 1) veces el peso total de S (como sucede con probabilidad constante) entonces el algoritmo duplica los pesos de cada elemento de V , y como antes repite este proceso hasta V se vuelve vacío. En cada iteración, se puede demostrar que el peso de la base óptima aumenta a una tasa mayor que el peso total de S , de lo cual se deduce que el algoritmo debe terminar dentro de 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 se puede interpretar como un método simplex dual . [17] Con ciertas primitivas de cálculo adicionales más allá de la prueba de violación y las primitivas de cálculo de base, este método puede hacerse determinista. [18]

Matoušek, Sharir y Welzl

Matoušek, Sharir & Welzl (1996) describen un algoritmo que usa una propiedad adicional de los programas lineales que no siempre es sostenida por 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 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 a la vez, o encontrar muestras de los elementos, Matoušek, Sharir y Welzl (1996) describen un algoritmo que elimina elementos uno a la vez. En cada paso mantiene una base C que inicialmente puede ser el conjunto de elementos ficticios. Puede describirse 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 }) luego  B  : = base ( B ∪ { x }) B  : = msw ( S , f , B ) return  B

En la mayoría de las llamadas recursivas del algoritmo, la prueba de violación se realiza correctamente 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 ny 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 del tiempo se pueden separar entre sí, lo que da como resultado un algoritmo que realiza pruebas de violación O ( dn ) en el algoritmo recursivo externo y un número que es exponencial en el raíz cuadrada de d log d en los niveles inferiores del algoritmo. [19]

Optimización con valores atípicos

Matoušek (1995) considera una variación de los problemas de optimización de tipo LP en los que se le da a uno, 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 planos. Demuestra 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 el tiempo O ( nk d ) , resolviendo un conjunto de O ( k d ) LP -type problemas 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, considere una colección de n puntos en el plano, cada uno de los cuales se mueve con velocidad constante. En cualquier momento, el diámetro de este sistema es la distancia máxima entre dos de sus puntos. El problema de encontrar un tiempo en el que se minimiza el diámetro se puede formular como minimizar el máximo puntual de O ( n 2 ) funciones cuasiconvexas, una para cada par de puntos, midiendo la distancia euclidiana entre el par en función del tiempo. Por lo tanto, se puede resolver como un problema de tipo LP de dimensión combinatoria dos en un conjunto de elementos O ( n 2 ) , 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 . Con el fin de aplicar su enfoque, debe existir un algoritmo de decisión que puede determinar, para un determinado tipo LP base 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 está por debajo de algún valor de umbral, encuentre el conjunto de elementos de tipo LP que determina y resuelva el problema explícito resultante de tipo LP.
  • De lo contrario, particione los valores de entrada en un número adecuado mayor que k de subconjuntos S i de igual tamaño .
  • Si f es la función objetivo para resolver el problema de tipo LP implícitamente definido, entonces defina una función g que mapee colecciones de subconjuntos S i al valor de f en la unión de la colección. Entonces, la colección de subconjuntos S i y la función objetivo g en sí define un problema de tipo LP, de la misma dimensión que el problema implícito a resolver.
  • Resuelva el problema de tipo LP (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 se pueden realizar mediante llamadas recursivas al algoritmo de Chan, y las pruebas de violación se pueden realizar mediante llamadas al algoritmo de decisión.

Con el supuesto de que el algoritmo de decisión toma una cantidad de tiempo O ( T ( n )) que crece al menos polinomialmente en 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 puede elegir de tal manera que el algoritmo de optimización de tipo LP implícito también se ejecute en el tiempo O ( T ( n )) .

Por ejemplo, para el diámetro mínimo de los 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 ) usando la técnica de calibradores giratorios . Por lo tanto, el algoritmo de Chan para encontrar el momento en el que se minimiza el diámetro también requiere tiempo O ( n log n ) . Chan usa este método para encontrar un punto de máxima profundidad de Tukey entre una colección dada de n puntos en el espacio euclidiano d- dimensional, en el tiempo O ( n d - 1 + n log n ) . Braß, Heinrich-Litan & Morin (2003) utilizaron una técnica similar para encontrar un punto de máxima profundidad de Tukey para la distribución uniforme en un polígono convexo.

El descubrimiento de algoritmos de tiempo lineal para programación lineal y la observación de que los mismos algoritmos podrían usarse 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 dio un tiempo esperado lineal. algoritmo para programas lineales de tres variables y el problema del círculo más pequeño. Sin embargo, Megido formuló la generalización de la programación lineal geométricamente en lugar de combinatoriamente, como un problema de optimización convexa más que como un problema abstracto en 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 podrían aplicarse tanto a programas convexos como a programas lineales. Dyer (1992) mostró que el problema del elipsoide envolvente mínimo también podría formularse como un problema de optimización convexa agregando 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 promovido 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 es de Sharir y Welzl (1992) , pero otros autores en el mismo período de tiempo formularon generalizaciones combinatorias alternativas de programas lineales. Por ejemplo, en un marco desarrollado por Gärtner (1995) , la función f se sustituye por un orden total en los subconjuntos de S . Es posible romper los lazos en un problema de tipo LP para crear un orden total, pero solo a expensas 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 programas lineales y problemas de complementariedad lineal , formulada por Stickney y Watson (1978) y posteriormente estudiada por varios otros autores, se refiere a las orientaciones de los bordes de un hipercubo con la propiedad de que cada cara del hipercubo (incluido el hipercubo completo como una cara) tiene un fregadero único , un vértice sin bordes salientes. Una orientación de este tipo puede formarse a partir de un problema de tipo LP haciendo corresponder 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 por orientando el borde entre los conjuntos vecinos A ⊆ B hacia B si f ( A ) ≠ f ( B ) y hacia A en caso contrario. La orientación resultante tiene la propiedad adicional de que forma un gráfico acíclico dirigido , a partir del cual se puede demostrar que un algoritmo aleatorio puede encontrar el sumidero único de todo el hipercubo (la base óptima del problema de tipo LP) en una serie de pasos. exponencial en la raíz cuadrada de  n . [22]

El marco desarrollado más recientemente de los espacios de infractores generaliza los problemas de tipo LP, en el sentido de que cada problema de tipo LP puede ser modelado por un espacio de infractores, pero no necesariamente al revés. Los espacios de infractores se definen de manera similar a los problemas de tipo LP, mediante una función f que asigna conjuntos a valores de función objetivo, pero los valores de f no están ordenados. A pesar de la falta de orden, cada conjunto S tiene un conjunto de bases bien definido (los conjuntos mínimos con el mismo valor que el conjunto completo) que se pueden encontrar mediante variaciones de los algoritmos de Clarkson para problemas de tipo LP. De hecho, se ha demostrado que los espacios de infractores caracterizan exactamente los sistemas que pueden resolverse con los algoritmos de Clarkson. [23]

  1. ↑ a b c Matoušek, Sharir y Welzl (1996) .
  2. ↑ Aunque Matoušek, Sharir y Welzl (1996) establecieron por primera vez que el problema del círculo más pequeño era un problema de tipo LP, varios artículos anteriores describieron algoritmos para este problema basados ​​en ideas de programación lineal de baja dimensión, incluido 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, Bern y Eppstein (1999) ; Eppstein (2005) .
  11. ^ Halman (2007) .
  12. ^ Amenta, Bern y Eppstein (1999) .
  13. ^ Puerto, Rodríguez-Chía y Tamir (2010) .
  14. ^ Eppstein (2006) .
  15. ^ Li (2007) .
  16. ↑ También se conocen loslímites de cola del 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. ↑ Chan (2004) dio la formulación de tipo LP de este problema, pero Gupta, Janardan y Smid (1996) lo estudiaron anteriormente utilizando otros métodos algorítmicos. Chan también cita un manuscrito inédito de Clarkson para unalgoritmo de tiempo O ( n log n ) , que coincide con el tiempo que puede lograrse mediante el enfoque implícito de tipo LP.
  21. ^ Matoušek (2009) .
  22. ^ Szabó y Welzl (2001) .
  23. ^ Gärtner y col. (2008) ; Brise y Gärtner (2011) .

  • Amenta, Nina (1994), "Teoremas 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 ; Berna, Marshall; Eppstein, David (1999), "Colocación óptima de puntos para suavizado de malla", 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 el entramado de números enteros" (PDF) , Studies in Applied Mathematics , 56 (2): 187–188, doi : 10.1002 / sapm1977562187 , MR  0462617.
  • Braß, Peter; Heinrich-Litan, Laura; Morin, Pat (2003), "Computación del centro del á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 de infractores" (PDF) , Computational Geometry: Theory and Applications , 44 (2): 70–81, arXiv : 0906.4706 , doi : 10.1016 / j.comgeo.2010.09.003 , Señor  2737285 , S2CID  1233875.
  • Chan, Timothy M. (2004), "Un algoritmo aleatorio óptimo para la máxima profundidad de Tukey" (PDF) , Proc. 15º ACM-SIAM Symp. Algoritmos discretos , págs. 423–429.
  • Chazelle, Bernard ; Matoušek, Jiří (1996), "Sobre algoritmos deterministas de tiempo lineal para problemas de optimización en dimensiones fijas" (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", Proc. Octavo Simposio sobre Geometría Computacional (SCG '92) , Berlín, Alemania, págs. 9-15, doi : 10.1145 / 142675.142681 , ISBN 0-89791-517-8, S2CID  7654513.
  • Dyer, Martin E .; Frieze, Alan M. (1989), "Un algoritmo aleatorio para programación lineal de dimensión fija", Programación matemática , (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 , Publicaciones MSRI, 52 , Cambridge Univ. Prensa, págs. 287–331, arXiv : cs.CG/0412046 , MR  2178325.
  • Eppstein, David (2006), "Análisis cuasiconvexo de ecuaciones de recurrencia multivariante 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 abstractos de optimización" (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), "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 , Señor  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 , Señor  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 con descuento son todos problemas de tipo LP" , Algorithmica , 49 (1): 37–50, doi : 10.1007 / s00453-007-0175 -3 , MR  2.344.393 , S2CID  8183965.
  • Kalai, Gil (1992), "Un algoritmo simplex aleatorio subexponencial", Proc. 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 ∞ con valores atípicos", Proc. Conf. IEEE sobre visión artificial y reconocimiento de patrones (CVPR '07) , págs. 1–8, doi : 10.1109 / CVPR.2007.383068 , hdl : 1885/39190 , S2CID  14882916.
  • Löffler, Maarten; van Kreveld, Marc (2010), "Cuadro delimitador más grande, diámetro más pequeño y problemas relacionados en puntos imprecisos" (PDF) , Teoría y aplicaciones de la geometría computacional , 43 (4): 419–433, doi : 10.1016 / j.comgeo. 2009.03.007 , MR  2575803.
  • Matoušek, Jiří (1995), "Sobre 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), "Eliminación de la degeneración en problemas de tipo LP revisados", Geometría discreta y computacional , 42 (4): 517–526, doi : 10.1007 / s00454-008-9085-7 , 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 cuando la dimensión es fija", Diario del ACM , 31 (1): 114-127, doi : 10.1145 / 2422.322418 , MR  0821388 , S2CID  12686747.
  • Nielsen, Frank; Nock, Richard (2008), "En el disco de información adjunto más pequeño" (PDF) , Cartas de procesamiento de información , 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), "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ñas dimensiones y cascos convexos simplificados", Geometría discreta y computacional , 6 (5): 423–434, doi : 10.1007 / BF02574699 , MR  1115100.
  • Sharir, Micha ; Welzl, Emo (1992), "Un destino combinatorio para la programación lineal y problemas relacionados", Noveno Simposio Anual sobre Aspectos Teóricos de la Computación (STACS), Cachan, Francia, 13-15 de febrero de 1992, Actas , Notas de conferencias en Ciencias de la Computación , 577 , Springer-Verlag, págs. 567–579, doi : 10.1007 / 3-540-55210-3_213.
  • Stickney, Alan; Watson, Layne (1978), "Modelos Digraph de algoritmos 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), "Unique sink orientations of cubes" (PDF) , 42º Simposio IEEE sobre Fundamentos de la informática (Las Vegas, NV, 2001) , págs. 547–555, doi : 10.1109 / SFCS.2001.959931 , MR  1948744 , S2CID  6597643.
  • Welzl, Emo (1991), "Discos envolventes más pequeños (bolas y elipsoides)", en Maurer, H. (ed.), New Results and New Trends in Computer Science (PDF) , Lecture Notes in Computer Science (555 ed.) , Springer-Verlag, págs. 359–370, doi : 10.1007 / BFb0038202.