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

Definición

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 asigna subconjuntos de S a valores de un conjunto totalmente ordenado. La función debe satisfacer dos propiedades clave:

• Monotonía: para 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 menor que B mismo, 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 en sí mismos 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 las mismas entradas) encuentra una base de B ∪ { x }. La tarea que debe realizar el algoritmo es evaluar f ( S ) utilizando solo estas evaluaciones restringidas o primitivas.

Ejemplos y aplicaciones

Bolas de LP

Un programa lineal puede definirse por un sistema de d variables reales no negativas , sujeto a n restricciones de desigualdad lineal, junto con una función objetivo lineal no negativa a minimizar. Esto puede ubicarse en el marco de 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 A . Con suposiciones de posición general adecuadas (para evitar que múltiples puntos de solución tengan el mismo valor óptimo de la función objetivo), esto satisface los requisitos de monotonía 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 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 monotonía como de localidad de un problema de tipo LP, con las mismas suposiciones 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 la monotonía (agregar 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 ∪ { 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 dimensión combinatoria tres, aunque se define utilizando geometría euclidiana bidimensional. ^[2] De manera más general, la bola envolvente más pequeña de puntos 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 cada una de un conjunto de bolas, ^[4] al problema de 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 más grande, d ( d + 3)/2 . ^[7]
• Sea K ₀ , K ₁ , ... una secuencia de n conjuntos convexos en un espacio euclidiano de dimensión d , y supongamos que deseamos encontrar el prefijo más largo de esta secuencia 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 se nos da una colección de cajas rectangulares alineadas en el eje en un espacio tridimensional y queremos encontrar una línea dirigida hacia el octante positivo del espacio que atraviese todas las cajas. Esto se puede expresar como un problema de tipo PL 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 las envolturas convexas 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, o d + 2 si tienen una intersección no vacía. ^[1]
• Sea S = { f ₀ , f ₁ , ... } 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 del círculo envolvente 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 de juegos algorítmicos , ^[11] mejorar la colocación de vértices en mallas de métodos de elementos finitos , ^[12] resolver problemas de ubicación de instalaciones , ^[13] analizar la complejidad temporal de ciertos algoritmos de búsqueda de tiempo exponencial, ^[14] y reconstruir las posiciones tridimensionales de los objetos a partir de sus imágenes bidimensionales. ^[15]

Algoritmos

Seidel

Seidel (1991) presentó 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, realiza pruebas de violación para cada uno y, dependiendo del resultado, realiza una llamada recursiva al mismo algoritmo con un conjunto más grande de elementos de 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 } devuelve  B

En un problema con dimensión combinatoria d , la prueba de violación en la iteración i ésima del algoritmo falla solo cuando x es uno de los d − | X | elementos base restantes, lo que ocurre con una probabilidad de 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 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 deben incluir al menos un elemento base:

función recursiva( S , f ) es  X  := conjunto vacío repetir  R  := un subconjunto aleatorio de S con 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( √ 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 √ 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 ² 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 máximo 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 que V se vacía. 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 que se deduce que el algoritmo debe terminar dentro de O(log n ) iteraciones.

Al utilizar 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 utilizando pruebas de violación O( dn + d ! d ^O(1) log n ) .

Cuando se aplica a un programa lineal, este algoritmo puede interpretarse como un método símplex dual . ^[17] Con ciertas primitivas computacionales adicionales más allá de la prueba de violación y las primitivas de cálculo de base, este método puede volverse 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, es decir, 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 añadiendo 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 añadir elementos de S de a uno por vez, o buscar muestras de los elementos, Matoušek, Sharir y Welzl (1996) describen un algoritmo que elimina elementos de a uno por vez. En cada paso mantiene una base C que inicialmente puede ser el conjunto de elementos ficticios. Puede describirse con el siguiente pseudocódigo:

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  := base( 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 declaració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 del tiempo se pueden separar entre sí, lo que da como resultado 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 los 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 hacer 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, considere una colección de n puntos en el plano, cada uno moviéndose con velocidad constante. En cualquier punto en el tiempo, el diámetro de este sistema es la distancia máxima entre dos de sus puntos. El problema de encontrar un momento en el que se minimice el diámetro puede formularse como la minimización del máximo puntual de O( n ² ) funciones cuasiconvexas, una para cada par de puntos, midiendo la distancia euclidiana entre el par como una función del tiempo. Por lo tanto, puede resolverse como un problema de tipo LP de dimensión combinatoria dos en 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 éste, en el que cada elemento de tipo LP está determinado por una k -tupla de valores de entrada, para una 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 está por debajo de un valor umbral, encuentre el conjunto de elementos de tipo LP que determina y resuelva el problema de tipo LP explícito 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 tipo PL implícitamente definido que se va a resolver, entonces se define una función g que mapea conjuntos de subconjuntos S _i al valor de f en la unión del conjunto. Entonces, el conjunto de subconjuntos S _i y la función objetivo g en sí definen un problema de tipo PL, de la misma dimensión que el problema implícito que se va a resolver.
• Resuelva el problema de tipo LP (explícito) definido por g utilizando el algoritmo de Clarkson, que realiza una cantidad lineal de pruebas de violación y una cantidad polilogarítmica 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.

Suponiendo que el algoritmo de decisión toma una cantidad de tiempo O( T ( n )) que crece al menos polinomialmente como 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 el 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 calibradores rotatorios . Por lo tanto, el algoritmo de Chan para encontrar el tiempo en el que se minimiza el diámetro también toma tiempo O( n log n ) . Chan utiliza este método para encontrar un punto de profundidad máxima de Tukey entre una colección dada de n puntos en el espacio euclidiano d -dimensional, en 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 profundidad máxima de Tukey para la distribución uniforme en un polígono convexo.

Historia y problemas relacionados

El descubrimiento de algoritmos de tiempo lineal para programación lineal y la observación de que los mismos algoritmos podrían en muchos casos usarse para resolver problemas de optimización geométrica que no fueran 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 lugar de como un problema abstracto sobre sistemas de conjuntos. De manera similar, Dyer (1986) y Clarkson (en la versión de 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 envolvente mínimo también podí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 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 monotonía es de Sharir & 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 reemplaza por un ordenamiento total en los subconjuntos de S . Es posible romper los empates en un problema de tipo LP para crear un ordenamiento 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 tanto de los programas lineales como de los problemas de complementariedad lineal , formulada por Stickney y Watson (1978) y estudiada posteriormente por varios 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 corresponder los subconjuntos de S con los vértices de un hipercubo de tal manera que dos subconjuntos difieran en un único elemento si y solo si los vértices correspondientes son adyacentes, y orientando la arista entre 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 un número de pasos exponencial en la raíz cuadrada de  n . ^[22]

El marco de trabajo más reciente de los espacios violadores generaliza los problemas de tipo PL, en el sentido de que cada problema de tipo PL puede ser modelado por un espacio violador, pero no necesariamente al revés. Los espacios violadores se definen de manera similar a los problemas de tipo PL, por 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 ordenación, cada conjunto S tiene un conjunto bien definido de bases (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 PL. De hecho, se ha demostrado que los espacios violadores caracterizan exactamente los sistemas que se pueden resolver mediante los algoritmos de Clarkson. ^[23]

Notas

1. Matoušek, Sharir y Welzl (1996).
2. Aunque Matoušek, Sharir y Welzl (1996) fueron los primeros en afirmar 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, incluidos Megiddo (1983) y Welzl (1991).
3. Fischer y Gärtner (2004).
4. Löffler y van Kreveld (2010).
5. Der (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); Epstein (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 conocen los límites de cola del tamaño de V : consulte 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 propuso 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 fue estudiada anteriormente 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 de tipo LP implícito.
21. Matoušek (2009).
22. Szabó y Welzl (2001).
23. 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), "Ubicació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 la red de números enteros" (PDF) , Estudios en Matemáticas Aplicadas , 56 (2): 187–188, doi :10.1002/sapm1977562187, MR  0462617.
• Braß, Peter; Heinrich-Litan, Laura; Morin, Pat (2003), "Cálculo 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 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", Proc. 8th Symposium on Computational Geometry (SCG '92) , Berlín, Alemania, págs. 9-15, doi :10.1145/142675.142681, ISBN 0-89791-517-8, Número de identificación del sujeto  7654513{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( 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.), Combinatorial and Computational Geometry , MSRI Publications, vol. 52, Cambridge Univ. Press, págs. 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 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 abstracta" (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, 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 , 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", Computational Geometry. Theory and Applications , 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 aleatorizado 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. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR '07) , págs. 1–8, doi :10.1109/CVPR.2007.383068, hdl : 1885/39190 , ISBN 978-1-4244-1179-5, Número de identificación del sujeto  14882916.
• Löffler, Maarten; van Kreveld, Marc (2010), "Cuadro delimitador más grande, diámetro más pequeño y problemas relacionados con puntos imprecisos" (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), "Revisión de 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 ³ 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", 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 más pequeño que contiene información" (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 de 1 centro planar por partes", 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 envolturas convexas simplificadas", Geometría discreta y computacional , 6 (5): 423–434, doi : 10.1007/BF02574699 , MR  1115100.
• Sharir, Micha ; Welzl, Emo (1992), "Un límite combinatorio para programación lineal y problemas relacionados", Stacs 92 , Lecture Notes in Computer Science, vol. 577, Springer-Verlag, págs. 567–579, doi :10.1007/3-540-55210-3_213, ISBN 978-3-540-55210-9.
• Stickney, Alan; Watson, Layne (1978), "Modelos dígrafos de algoritmos de tipo Bard para el problema de complementariedad lineal", Matemáticas de la investigación de operaciones , 3 (4): 322–333, doi :10.1287/moor.3.4.322, MR  0509668.
• Szabó, Tibor; Welzl, Emo (2001), "Orientaciones únicas de sumideros de cubos" (PDF) , 42.º Simposio IEEE sobre fundamentos de la informática (Las Vegas, NV, 2001) , págs. 547–555, doi :10.1109/SFCS.2001.959931, ISBN 0-7695-1390-5, MR  1948744, S2CID  6597643.
• Welzl, Emo (1991), "Los 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 (555 ed.), Springer-Verlag, págs. 359–370, doi :10.1007/BFb0038202, ISBN 3-540-54869-6.