Problemas algorítmicos sobre conjuntos convexos

Muchos problemas de programación matemática pueden formularse como problemas sobre conjuntos convexos o cuerpos convexos . Seis tipos de problemas son particularmente importantes: ^[1]^{: Sec.2} optimización , violación , validez , separación , pertenencia y vacío . Cada uno de estos problemas tiene una variante fuerte (exacta) y una variante débil (aproximada).

En todas las descripciones de problemas, K denota un conjunto compacto y convexo en R ⁿ .

Variantes fuertes

Las variantes fuertes de los problemas son: ^[1]^{: 47}

Problema de optimización fuerte (SOPT) : dado un vector c en R ⁿ , encontrar un vector y en K tal que c ^Ty ≥ c ^Tx para todo x en K , o afirmar que K está vacío.
Problema de violación fuerte (SVIOL) : dado un vector c en R ⁿ y un número t , decidir si c ^Tx ≤ t para todo x en K , o encontrar y en K tal que c ^Ty > t .
Problema de validez fuerte (SVAL) : dado un vector c en R ⁿ y un número t , decidir si c ^Tx ≤ t para todo x en K .
Problema de no vacío fuerte (SNEMPT) : decide si K está vacío y, si no lo está, encuentra un punto en K.
Problema de separación fuerte (SSEP) : dado un vector y en R ⁿ , decidir si y está en K , y si no, encontrar un hiperplano que separe y de K , es decir, encontrar un vector c en R ⁿ tal que c ^Ty > c ^Tx para todo x en K .
Problema de membresía fuerte (SMEM) : dado un vector y en R ⁿ , decidir si y en K .

Estrechamente relacionado con los problemas sobre conjuntos convexos está el siguiente problema sobre una función convexa f : R ⁿ → R :

Minimización de funciones convexas sin restricciones fuertes (SUCFM) : encuentre un vector y en R ⁿ tal que f( y ) ≤ f( x ) para todo x en R ⁿ .

Implicaciones triviales

De las definiciones se desprende claramente que los algoritmos para algunos de los problemas se pueden utilizar para resolver otros problemas en tiempo polinomial oracular:

Un algoritmo para SOPT puede resolver SVIOL, verificando si c ^Ty > t;
Un algoritmo para SVIOL resuelve SVAL de manera trivial.
Un algoritmo para SVIOL puede resolver SNEMPT, tomando c = 0 y t = -1.
Un algoritmo para SSEP resuelve SMEM de manera trivial.

Ejemplos

La resolubilidad de un problema depende fundamentalmente de la naturaleza de K y de la forma en que se representa. Por ejemplo:

Si K está representado por un conjunto de algunas m desigualdades lineales, entonces SSEP (y por lo tanto SMEM) es trivial: dado un vector y en R ⁿ , simplemente verificamos si satisface todas las desigualdades y, si no, devolvemos una desigualdad violada como el hiperplano separador. SOPT se puede resolver utilizando programación lineal , pero no es tan trivial.
Si K se representa como la envoltura convexa de algunos m puntos, entonces SOPT (y por lo tanto SVIOL, SVAL y SNEMPT) es fácil de resolver evaluando el objetivo en todos los vértices. SMEM requiere verificar si existe un vector que sea una combinación convexa de los vértices, lo que requiere programación lineal. SSEP también requiere un certificado en caso de que no haya solución.
Si K se representa como el epígrafe de alguna función convexa computable , entonces SMEM es trivial; si se puede calcular un subgradiente , entonces SSEP también es fácil.

Variantes débiles

Cada uno de los problemas anteriores tiene una variante débil, en la que la respuesta se da sólo de forma aproximada. Para definir la aproximación, definimos las siguientes operaciones sobre conjuntos convexos: ^[1]^{: 6}

S( K , ε ) es la bola de radio ε alrededor de K , definida como {x en R ⁿ : |xy| ≤ ε para algún y en K }. De manera informal, un punto en S( K , ε ) está en K o "casi" en K .
S( K , -ε ) es la ε-bola interior de K , definida como {x en K : cada y con |xy| ≤ ε está en K }. De manera informal, un punto en S( K , -ε ) está "muy dentro" de K .

Utilizando estas nociones, las variantes débiles son: ^[1]^{: 50}

Problema de optimización débil (WOPT) : dado un vector c en Q ⁿ y un racional ε >0, o bien:
- Encuentra un vector y en S ( K,ε ) tal que c ^Ty + ε ≥ c ^Tx para todo x en S ( K,-ε ), o -
- afirmar que S ( K,-ε ) está vacío.
Problema de violación débil (WVIOL) : dado un vector c en Q ⁿ , un número racional t y un ε racional >0, o bien:
- afirmar que c ^Tx ≤ t + ε para todo x en S ( K,-ε ), o -
- Encuentra una y en S ( K,ε ) tal que c ^Ty > t - ε .
Problema de validez débil (WVAL) : dado un vector c en Q ⁿ , un número racional t y un ε racional >0, o bien:
- afirmar que c ^Tx ≤ t + ε para todo x en S ( K,-ε ), o -
- afirmar que c ^Ty ≥ t-ε para algún y en S ( K,ε ) .
Problema de no vacío débil (WNEMPT) : Dado un ε racional >0, o bien:
- afirmar que S(K,-ε) está vacío, o -
- Encuentra un punto y en S(K,ε) .
Problema de separación débil (WSEP) : dado un vector y en Q ⁿ y un racional ε >0, o bien:
- afirmar que y en S ( K,ε ), o -
- Encuentra un vector c en Q ⁿ (con || c || _∞ =1) tal que c ^Ty + ε > c ^Tx para todo x en S(K,-ε) .
Problema de membresía débil (WMEM) : dado un vector y en Q ⁿ , y un racional ε >0, o bien -
- afirmar que y en S ( K,ε ), o -
- afirmar que y no está en S ( K,-ε ). Estrechamente relacionado con los problemas sobre conjuntos convexos está el siguiente problema sobre un conjunto convexo compacto K y una función convexa f : R ⁿ → R dada por un oráculo de valor aproximado:
Minimización de funciones convexas débilmente restringidas (WCCFM) : dado un racional ε >0, encuentre un vector en S ( K,ε ) tal que f( y ) ≤ f( x ) + ε para todo x en S(K,-ε) .

Implicaciones triviales

De manera análoga a las variantes fuertes, los algoritmos para algunos de los problemas se pueden utilizar para resolver otros problemas en tiempo oracular-polinomial:

Un oráculo para WOPT puede resolver WVIOL, verificando si c ^Ty + ε > t ;
Un oráculo para WVIOL resuelve WVAL de manera trivial.
Un oráculo para WVIOL puede resolver WNEMPT, tomando c = 0 y t = -1.
Se puede utilizar un oráculo para WSEP para resolver WMEM.

Variantes débiles más fuertes

Algunas de estas variantes débiles pueden fortalecerse ligeramente. ^[1]^{: Rem.2.1.5(a)} Por ejemplo, WVAL con entradas c , t ' = t + ε /2 y ε ' = ε /2 hace una de las siguientes cosas:

afirmar que c ^Tx ≤ t + ε para todo x en S ( K,-ε /2), o -
afirmar que c ^Ty ≥ t para algún y en S ( K,ε /2) .

Implicaciones de las variantes débiles

Además de estas implicaciones triviales, existen implicaciones altamente no triviales, cuya demostración se basa en el método del elipsoide . Algunas de estas implicaciones requieren información adicional sobre el cuerpo convexo K. En particular, además del número de dimensiones n , puede ser necesaria la siguiente información: ^[1]^{: 53}

Un radio circunscrito R, que es el radio de una bola centrada en el origen que contiene a K. La tupla ( K ; n , R ) se denomina conjunto convexo circunscrito .
Un radio inscrito r , que es el radio de una bola contenida en K en caso de que K no esté vacío. Este r también proporciona un límite inferior para el volumen de K . La tupla ( K ; n , R ,r) se denomina conjunto convexo bien acotado .
Un punto interior a ₀ , que es un punto tal que una bola de radio r alrededor de a ₀ está contenida en K . La tupla ( K ; n , R , r , a ₀ ) se denomina conjunto convexo centrado .

Lo siguiente se puede hacer en tiempo polinomial oráculo: ^[1]^{: Sec.4}

Un oráculo para WSEP, con un radio circunscrito R , puede resolver WVIOL. Este algoritmo utiliza el método del elipsoide de corte central . Otra opción es utilizar otro método que utilice símplices en lugar de elipsoides. ^[2]
Un oráculo para WVIOL, con un radio circunscrito R , puede resolver WOPT usando búsqueda binaria .
Un oráculo para WSEP, con un radio circunscrito R , puede resolver WOPT. Esto se deduce por transitividad de las implicaciones WSEP→WVIOL y WVIOL→WOPT, pero también existe un algoritmo directo WSEP→WOPT que utiliza la técnica de función objetivo deslizante . ^[3]
Un oráculo para WMEM, con R y r y un ₀ , puede resolver WVIOL. Esto fue demostrado por Yudin y Nemirovskii en 1976, ^[4] utilizando el método del elipsoide de corte superficial .
Un oráculo para WMEM, con R y r y un ₀ , puede resolver WOPT. Esto se deduce por transitividad de las implicaciones WMEM→WVIOL y WVIOL→WOPT.
Un oráculo para WMEM, con R y r y un ₀ , puede resolver WSEP. Esto se deduce por transitividad de las implicaciones WMEM→WVIOL y WVIOL→WSEP. Curiosamente, ambos pasos requieren el método del elipsoide y no se conoce ningún algoritmo directo WMEM→WSEP.
Un oráculo para WOPT puede resolver WCCFM. ^[1]^{: 56}
- Se puede utilizar un oráculo de valor aproximado para una función convexa para construir un oráculo WMEM. Al combinar esto con las implicaciones WMEM→WVIOL y WVIOL→WOPT y WOPT→WCCFM, se deduce que WCCFM en un cuerpo convexo centrado ( K ; n , R , r , a ₀ ) dado por un oráculo WMEM se puede resolver en tiempo polinomial. ^[1]^{: 113}
Se puede utilizar un oráculo para WOPT, con r , para encontrar r' y a ₀ tales que S( a ₀ ,r') esté contenido en K .

Las siguientes implicaciones utilizan el conjunto polar de K , definido como . Nótese que K **= K . $K^{*}:=\{y\in \mathbb {R} ^{n}:y^{T}x\leq 1{\text{ para todo }}x\in K\}$

Un oráculo para WVAL en un cuerpo convexo centrado en 0 (K; n,R,r,0) puede resolver WMEM en K *.
Un oráculo para WVIOL en un cuerpo convexo centrado en 0 (K; n,R,r,0) puede resolver WSEP en K *.
Un oráculo para WOPT puede resolver WSEP sin más información. La prueba utiliza argumentos de polaridad.
Un oráculo para WVAL, con un radio circunscrito R , puede resolver WSEP. La prueba utiliza argumentos de polaridad.

Necesidad de información adicional

Algunas de las implicaciones anteriores probablemente no funcionen sin la información adicional. ^[1]^{: Sec.4.5}

Un oráculo para WMEM o incluso para SMEM, con R y r pero sin un ₀ , no puede resolver WVIOL en politiempo, incluso para n = 1 y r = 1 y c = 1 y ε = 1. Demostración . Nótese que con los parámetros dados, lo que sabemos sobre K es que K está contenido en el intervalo [- R , R ], y contiene algún intervalo de longitud 2 r = 2. Supongamos que un oráculo SMEM responde "no" a las primeras R consultas de pertenencia; esta es una secuencia válida de respuestas, ya que por el principio del palomar, hay un intervalo de longitud 2 que no contiene ningún punto consultado. Por lo tanto, cualquier algoritmo que resuelva WOPT necesita más de R consultas, por lo que es exponencial en la longitud de codificación de R .
De manera similar, un algoritmo para WMEM, con R y r pero sin un ₀ , no puede resolver WOPT.
Un oráculo para WVAL, con r y un ₀ pero sin R , no puede resolver WVIOL.
Un oráculo para WVIOL, con r y un ₀ pero sin R , no puede resolver WOPT y no puede resolver WMEM.
Un oráculo para WMEM, con r y un ₀ pero sin R , no puede resolver WSEP.
Un oráculo para WSEP, con r y un ₀ pero sin R , no puede resolver WVAL.
No se puede utilizar un oráculo para WSEP con r para derivar un ₀ y, por lo tanto, no se puede utilizar para resolver WOPT.
No se puede utilizar un oráculo para WVIOL con r para derivar un ₀ y, por lo tanto, no se puede utilizar para resolver WOPT.
No se puede utilizar un oráculo para WSEP con R para derivar r.

Problemas geométricos sobre cuerpos convexos

Utilizando los problemas básicos anteriores, se pueden resolver varios problemas geométricos relacionados con cuerpos convexos. En particular, se puede encontrar un elipsoide de John aproximado en tiempo polinomial oráculo: ^[1]^{: Sec.4.6}

Dado un cuerpo convexo bien acotado (K; n, R, r) descrito por un oráculo WSEP, se puede encontrar un elipsoide E( A , a ) tal que . El algoritmo utiliza el método de elipsoide de corte superficial . Nótese que, por el teorema de Lowner-John, existe un elipsoide que satisface una relación más fuerte , pero ese teorema no produce un algoritmo de politiempo. $E\left({\frac {1}{n(n+1)^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$ $E\left({\frac {1}{n^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$
Dado un cuerpo convexo centralmente simétrico y bien acotado (K; n, R, r) descrito por un oráculo WSEP, se puede encontrar un elipsoide E( A , a ) tal que . Nótese que un teorema de Jordan demuestra que existe un elipsoide que satisface una relación más fuerte , pero ese teorema no produce un algoritmo de politiempo. $E\left({\frac {1}{n(n+1)}}A,a\right)\subseteq K\subseteq E(A,a)$ $E\left({\frac {1}{n}}A,a\right)\subseteq K\subseteq E(A,a)$
Dado un cuerpo convexo bien acotado (K; n, R, r) dado como el conjunto solución de un sistema de desigualdades lineales, se puede encontrar un elipsoide E( A , a ) tal que . $E\left({\frac {1}{(n+1)^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$
Dado un cuerpo convexo bien acotado y centralmente simétrico (K; n, R, r) dado como el conjunto solución de un sistema de desigualdades lineales, se puede encontrar un elipsoide E( A , 0 ) tal que . $E\left({\frac {1}{n+1}}A,0\right)\subseteq K\subseteq E(A,0)$

Estos resultados implican que es posible aproximar cualquier norma mediante una norma elipsoidal. Específicamente, supongamos que una norma N está dada por un oráculo de norma débil : para cada vector x en Q ⁿ y cada racional ε >0, devuelve un número racional r tal que |N( x )- r |< ε . Supongamos que también conocemos una constante c ₁ que da un límite inferior en la relación de N( x ) con la norma euclidiana. Entonces podemos calcular en tiempo de oráculo-polinomio una transformación lineal T de R ⁿ tal que, para todo x en R ⁿ , . $c_{1}\|x\|\leq N(x)$ $\|Tx\|\leq N(x)\leq {\sqrt {n(n+1)}}\|Tx\|$

También es posible aproximar el diámetro y el ancho de K :

Dado un cuerpo convexo bien acotado ( K ; n , R , r ) descrito por un oráculo WSEP, su diámetro se puede aproximar encontrando dos puntos x , y en K , y una bola con radio R* que contiene a K , tales que . $R^{*}\leq {\frac {1}{2}}{\sqrt {n}}\|xy\|$
Dado un cuerpo convexo bien acotado ( K ; n , R , r ) descrito por un oráculo WSEP, su ancho se puede aproximar encontrando dos hiperplanos paralelos c ^T x=d ₁ y c ^T x=d ₂ que se encuentran en dos lados de K , y una bola con radio r* contenida en K , tales que $r^{*}={\frac {d_{2}-d_{1}}{2(n+1){\sqrt {n}}\|c\|}}$

Algunos problemas aún no resueltos (a fecha de 1993) son si es posible calcular en politiempo el volumen, el centro de gravedad o el área de superficie de un cuerpo convexo dado por un oráculo de separación.

Problemas sobre combinaciones de conjuntos convexos

Algunas operaciones binarias sobre conjuntos convexos preservan las propiedades algorítmicas de los distintos problemas. En particular, dados dos conjuntos convexos K y L : ^[1]^{: Sec.4.7}

Para la suma K+L, WOPT se puede resolver en tiempo polinomial utilizando oráculos WOPT para K y L. Lo mismo se aplica a WVIOL, WSEP y WVAL. Sin embargo, no se aplica lo mismo a WMEM, a menos que K y L sean cuerpos convexos centrados.
Para la unión conv(K u L), los resultados son los mismos para la suma: WOPT, WVIOL, WSEP y WVAL (pero no WMEM) se pueden resolver en politiempo utilizando los oráculos respectivos para K y L.
Para la intersección K ח L, puede resultar imposible calcular el radio interior en tiempo polifónico, por lo que necesitamos conocer el radio interior de antemano. Con este conocimiento, los cinco problemas (WMEM, WOPT, WVIOL, WSEP y WVAL) se pueden resolver en tiempo polifónico utilizando los oráculos respectivos para K y L.
Dados los oráculos WSEP para K y L, y un número racional r > 0, es posible en tiempo de oráculo-polinomio devolver (a) una afirmación de que la intersección K ח L contiene una bola con radio r , o (b) un vector c con tamaño 1, y un número d, tal que c ^T x ≤ d para todo x en S(K,-ε) y c ^T x ≥ d para todo x en S(L,-ε), donde ε=9nr ³ (R _K /r _K + R _L /r _L ). Es decir: o bien la intersección contiene una bola, o bien hay un hiperplano que casi separa a K de L.

De oráculos débiles a oráculos fuertes

En algunos casos, un oráculo para un problema débil se puede utilizar para resolver el problema fuerte correspondiente.

Conjuntos convexos generales

Un algoritmo para WMEM, dado un radio circunscrito R y un radio de inscripción r y un punto interior a ₀ , puede resolver el siguiente problema de pertenencia ligeramente más fuerte (aún más débil que SMEM): dado un vector y en Q ⁿ , y un racional ε >0, o bien afirmar que y está en S ( K,ε ), o bien afirmar que y no está en K. La prueba es elemental y utiliza una única llamada al oráculo WMEM. ^[1]^{: 108}

Poliedros

Supongamos ahora que K es un poliedro . Entonces, se pueden usar muchos oráculos para problemas débiles para resolver los problemas fuertes correspondientes en tiempo de oráculo-polinomio. Las reducciones requieren un límite superior en la complejidad de representación ( complejidad de facetas o complejidad de vértices ) del poliedro: ^[1]^{: Sec. 6.3}

Un oráculo para WNEMPT, para un poliedro de dimensión completa P con un límite en su complejidad de representación, puede resolver SNEMPT.
Un oráculo para WOPT, para un poliedro P de dimensión completa acotado con un límite en su complejidad de representación, puede resolver SOPT.
Un oráculo para WVIOL, para un poliedro P de dimensión completa acotado con un límite en su complejidad de representación, puede resolver SVIOL.
Un oráculo para WVAL, para un poliedro P de dimensión completa acotado con un límite en su complejidad de representación, puede resolver SVAL.
Un oráculo para WSEP, para un poliedro P de dimensión completa acotado con un límite en su complejidad de representación, puede resolver SSEP.
Un oráculo para WMEM, para un poliedro P de dimensión completa acotado con un límite en su complejidad de representación, dado un punto interior en P , puede resolver SMEM.

Las pruebas utilizan resultados de aproximación diofántica simultánea .

Necesidad de información adicional

¿Qué importancia tiene la información adicional para las reducciones mencionadas anteriormente? ^[1]^{: 173}

La suposición de que P es de dimensión completa es esencial: si P no es de dimensión completa, entonces la esfera interior S( K , -ε ) está vacía. Por lo tanto, cualquier oráculo para resolver un problema débil no puede distinguir entre P y el conjunto vacío.
La suposición de que P está acotado puede relajarse: es posible definir variantes de los problemas débiles para poliedros que pueden no estar acotados y probar reducciones análogas a los resultados anteriores.
Para la implicación WMEM→SMEM, la suposición de que se da un punto interior de P es esencial. Demostración : Supongamos que tenemos un poliedro P con complejidad de vértice conocida 2 n , y deseamos decidir si 0 está en P . Si le hacemos al oráculo WMEM menos de 2 ⁿ consultas, entonces el oráculo siempre puede responder "no", y es posible que exista un cubo unitario H con vértices cuyos coeficientes están en {0,+1,-1}, que contiene cero como vértice, pero no contiene ninguno de los puntos consultados. Por lo tanto, es posible que P = H y la respuesta sea "sí", pero también es posible que P sea la envoltura convexa de todos los vértices no cero de H y la respuesta sea "no". Por lo tanto, ningún algoritmo politemporal puede resolver SMEM.

Implicaciones de las variantes fuertes

Utilizando los resultados anteriores, es posible probar implicaciones entre variantes fuertes. Lo siguiente se puede hacer en tiempo de oráculo-polinomio para un poliedro bien descrito - un poliedro para el cual se conoce un límite superior en la complejidad de representación : ^[1]^{: Sec.6.4}

Un oráculo para SSEP puede resolver SNEMPT, ^[1]^{: Thm.6.4.1}
Se puede utilizar un oráculo para cada SSEP, SVIOL, SOPT para resolver los otros dos. ^[1]^{: Thm.6.4.9}
En el caso especial en que P es un cono, SVIOL para P es lo mismo que SSEP para su cono polar P *; por lo tanto, un oráculo SSEP para P produce un algoritmo SSEP para P *.
Si sabemos de antemano que P no está vacío, entonces el oráculo SSEP puede ser reemplazado por un oráculo de separación ligeramente más débil: dado un vector y en Q ⁿ , si y no está en P encuentra un hiperplano que separa y de P (= un vector c en R ⁿ tal que c ^Ty > c ^Tx para todo x en P ), pero si y está en P , todavía puede devolver un hiperplano - un vector c en R ⁿ tal que c ^Ty ≥ c ^Tx para todo x en P .

Por lo tanto, SSEP, SVIOL y SOPT son todos equivalentes en tiempo polinómico. Esta equivalencia, en particular, implica la prueba de Khachian de que la programación lineal se puede resolver en tiempo polinómico, ^[1]^{: Thm.6.4.12} ya que cuando un poliedro está dado por desigualdades lineales explícitas, un oráculo SSEP es trivial de implementar. Además, una solución dual óptima básica también se puede encontrar en tiempo polinómico. ^[1]^{: Thm.6.5.14}

Téngase en cuenta que los teoremas anteriores no requieren una suposición de dimensionalidad completa o un límite inferior en el volumen.

No se podrán realizar otras reducciones sin información adicional:

Si P no es de dimensión completa, entonces SMEM no puede resolver SSEP, SVIOL o SOPT.
Si P no tiene límites, entonces SVAL no puede resolver SSEP, SVIOL o SOPT.

Extensión a conjuntos convexos no bien descritos

Jain ^[5] extiende uno de los teoremas anteriores a conjuntos convexos que no son poliedros y no están bien descritos. Sólo exige una garantía de que el conjunto convexo contiene al menos un punto (no necesariamente un vértice) con una longitud de representación acotada. Demuestra que, bajo este supuesto, SNEMPT puede resolverse (se puede encontrar un punto en el conjunto convexo) en politiempo. ^[5]^{: Teoría 12} Además, la longitud de representación del punto encontrado es como máximo P( n ) veces el límite dado, donde P es alguna función polinómica. ^[5]^{: Teoría 13}

Problemas geométricos sobre poliedros

Utilizando los problemas básicos anteriores, se pueden resolver varios problemas geométricos relacionados con politopos y poliedros no vacíos con un límite en la complejidad de representación, en tiempo oráculo-polinomial, dado un oráculo para SSEP, SVIOL o SOPT: ^[1]^{: Sec.6.5}

Encuentra un vértice de P .
Dado un vector c , encuentre un vértice de P que maximice c ^Tx .
Dados los vectores c ₁ , c ₂ , encuentre un vértice de P que maximice c ₁^Tx , y sujeto a esto, maximice c ₂^Tx ( maximización lexicográfica ).
Encuentra la envoltura afín de P . ^[6] Esto también implica encontrar la dimensión de P , y un punto en el interior relativo de P .
Decide si dos vectores dados son vértices de P y, de ser así, si son adyacentes.
Dado un punto en P , escríbalo como una combinación convexa de como máximo n vértices de P (una versión algorítmica del teorema de Carathéodory ).

Véase también

Oráculo de separación : un algoritmo para resolver el problema de separación (débil o fuerte) para algún conjunto convexo K.

Referencias

^ abcdefghijklmnopqrstu Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, Sr. 1261419
^ Yamnitsky, Boris; Levin, Leonid A. (1982). "Un antiguo algoritmo de programación lineal se ejecuta en tiempo polinomial". 23.º Simposio Anual sobre Fundamentos de la Ciencia de la Computación (SFCS 1982) . págs. 327–328. doi :10.1109/SFCS.1982.63 . Consultado el 29 de enero de 2024 .
^ Bland, Robert G.; Goldfarb, Donald; Todd, Michael J. (diciembre de 1981). "Artículo destacado: El método elipsoide: una encuesta". Investigación de operaciones . 29 (6): 1039–1091. doi :10.1287/opre.29.6.1039. ISSN 0030-364X.
^ Yudin y Nemirovskii, 1976, https://elibrary.ru/item.asp?id=38308898 (en ruso)
^ abc Jain, Kamal (2007). "Un algoritmo de tiempo polinomial para calcular un equilibrio de mercado Arrow-Debreu para servicios públicos lineales". Revista SIAM de informática . 37 (1): 303–318. doi :10.1137/S0097539705447384. ISSN 0097-5397.
^ Edmonds, J.; Pulleyblank, WR; Lovász, L. (1982-09-01). "Descomposiciones de ladrillos y el rango coincidente de grafos". Combinatorica . 2 (3): 247–274. doi :10.1007/BF02579233. ISSN 1439-6912. S2CID 37135635.