Problemas algorítmicos en conjuntos convexos.

Muchos problemas de programación matemática se pueden formular como problemas sobre conjuntos convexos o cuerpos convexos . Seis tipos de problemas son particularmente importantes: ^{[1] : Sección 2} optimización , violación , validez , separación , membresía 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 ⁿ , encuentre un vector y en K tal que c ^T y ≥ c ^T x para todo x en K , o afirme que K está vacío.
• Problema de violación fuerte (SVIOL) : dado un vector c en R ⁿ y un número t , decida si c ^T x ≤ t para todo x en K , o encuentre y en K tal que c ^T y > t .
• Problema de validez fuerte (SVAL) : dado un vector c en R ⁿ y un número t , decida si c ^T x ≤ t para todo x en K .
• Problema fuerte de no vacío ( SNEMPT) : decida si K está vacío y, en caso contrario, encuentre un punto en K.
• Problema de separación fuerte (SSEP) : dado un vector y en R ⁿ , decidir si y en K , y si no, encontrar un hiperplano que separe y de K , es decir, encontrar un vector c en R ⁿ tal que c ^T y > c ^T x para todo x en K .
• Problema de membresía fuerte ( SMEM) : dado un vector y en R ⁿ , decida si y en K.

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

• Minimización fuerte de función convexa sin restricciones (SUCFM) : encuentre un vector y en R ⁿ tal que f( y ) ≤ f( x ) para todo x en R ⁿ .

Implicaciones triviales

De las definiciones, queda claro que los algoritmos para algunos de los problemas se pueden usar para resolver otros problemas en tiempo polinomial de Oracle:

• Un algoritmo para SOPT puede resolver SVIOL, comprobando si c ^T y > t;
• Un algoritmo para SVIOL resuelve SVAL de forma trivial.
• Un algoritmo para SVIOL puede resolver SNEMPT, tomando c =0 yt = -1.
• Un algoritmo para SSEP resuelve SMEM de forma trivial.

Ejemplos

La solucion de un problema depende crucialmente 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 hiperplano separador. SOPT se puede resolver mediante programación lineal , pero no es tan trivial.
• Si K se representa como el casco convexo de algunos m puntos, entonces SOPT (y por 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 el 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 en conjuntos convexos: ^{[1] : 6}

• S( K , ε ) es la bola de radio ε alrededor de K , definida como {x en R ⁿ  : |xy| ≤ ε para alguna y en K }. Informalmente, 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 }. Informalmente, un punto en S( K , -ε ) "muy dentro" K .

Usando 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, ya sea -
  • encuentre un vector y en S ( K,ε ) tal que c ^T y + ε ≥ c ^T x 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, ya sea -
  • afirmar que c ^T x ≤ t + ε para todo x en S ( K,-ε ), o -
  • encuentre una y en S ( K,ε ) tal que c ^T y > t - ε .
• Problema de validez débil (WVAL) : dado un vector c en Q ⁿ , un número racional t y un ε racional >0, ya sea -
  • afirmar que c ^T x ≤ t + ε para todo x en S ( K,-ε ), o -
  • afirmar que c ^T y ≥ t-ε para algún y en S ( K,ε ) .
• Problema de no vacío débil (WNEMPT) : dado un ε racional > 0, ya sea -
  • afirmar que S(K,-ε) está vacío, o -
  • encuentre un punto y en S(K,ε) .
• Problema de separación débil (WSEP) : dado un vector y en Q ⁿ y un ε racional >0, ya sea -
  • afirmar que y en S ( K,ε ), o -
  • encuentre un vector c en Q ⁿ (con || c || _∞ =1) tal que c ^T y + ε > c ^T x para todo x en S(K,-ε) .
• Problema de membresía débil (WMEM) : dado un vector y en Q ⁿ y un ε racional >0, ya sea -
  • 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 función convexa restringida débil (WCCFM) : dado un ε >0 racional , 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 polinomial de Oracle:

• Un oráculo para WOPT puede resolver WVIOL, comprobando si c ^T y + ε > t ;
• Un oráculo para WVIOL resuelve WVAL de forma trivial.
• Un oráculo para WVIOL puede resolver WNEMPT, tomando c =0 yt = -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 reforzarse ligeramente. ^{[1] : Rem.2.1.5(a)} Por ejemplo, WVAL con entradas c , t ' = t + ε /2 y ε ' = ε /2 realiza una de las siguientes acciones:

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

Implicaciones de variantes débiles

Además de estas implicaciones triviales, existen implicaciones muy no triviales, cuya prueba 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 K. La tupla ( K ; n , R ) se llama 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. Esta 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 llama conjunto convexo centrado .

Lo siguiente se puede hacer en tiempo polinómico de Oracle: ^{[1] : Sección 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ímbolos simples en lugar de elipsoides. ^[2]
• Un oráculo para WVIOL, con un radio circunscrito R , puede resolver WOPT mediante búsqueda binaria .
• Un oráculo para WSEP, con un radio circunscrito R , puede resolver WOPT. Esto se deriva de la transitividad de las implicaciones WSEP→WVIOL y WVIOL→WOPT, pero también existe un algoritmo directo WSEP→WOPT que utiliza la técnica de la función objetivo deslizante . ^[3]
• Un oráculo para WMEM, con R y r y a ₀ , 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 a ₀ , puede resolver WOPT. Esto se sigue por transitividad de las implicaciones WMEM→WVIOL y WVIOL→WOPT.
• Un oráculo para WMEM, con R y r y a ₀ , puede resolver WSEP. Esto se sigue 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. Combinando esto con las implicaciones WMEM→WVIOL y WVIOL→WOPT y WOPT→WCCFM implica 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 un ₀ tal que S( a ₀ ,r') esté contenido en K .

Las siguientes implicaciones utilizan el conjunto polar de K -definido como . Tenga en cuenta que K **= K . ${\displaystyle K^{*}:=\{y\in \mathbb {R} ^{n}:y^{T}x\leq 1{\text{ for all }}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

Es probable que algunas de las implicaciones anteriores no funcionen sin información adicional. ^{[1] : Sección 4.5}

• Un oráculo para WMEM o incluso para SMEM, con R y r pero sin ₀ , no puede resolver WVIOL en politiempo, incluso para n =1 y r =1 y c =1 y ε =1. Prueba . Tenga en cuenta que con los parámetros dados, lo que sabemos acerca de 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 consultas de membresía de R ; esta es una secuencia válida de respuestas, ya que por el principio de casillero, hay un intervalo de longitud 2 que no contiene ningún punto consultado. Por lo tanto, cualquier algoritmo que resuelva WOPT necesita más que consultas R , 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 0 _, no puede resolver WOPT.
• _Un oráculo para WVAL, con r y 0 pero sin R , no puede resolver WVIOL.
• _Un oráculo para WVIOL, con r y 0 pero sin R , no puede resolver WOPT ni WMEM.
• _Un oráculo para WMEM, con r y 0 pero sin R , no puede resolver WSEP.
• _Un oráculo para WSEP, con r y 0 pero sin R , no puede resolver WVAL.
• Un oráculo para WSEP con r no se puede usar para derivar un ₀ y, por lo tanto, no se puede usar para resolver WOPT.
• Un oráculo para WVIOL con r no se puede usar para derivar un ₀ y, por lo tanto, no se puede usar para resolver WOPT.
• No se puede utilizar un oráculo para WSEP con R para derivar r.

Problemas geométricos en 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 polinómico de Oracle: ^{[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 del elipsoide de corte superficial . Tenga en cuenta que, según el teorema de Lowner-John, existe un elipsoide que satisface una relación más fuerte , pero ese teorema no produce un algoritmo politiempo. ${\displaystyle E\left({\frac {1}{n(n+1)^{2}}}A,a\right)\subseteq K\subseteq E(A,a)}$ ${\displaystyle E\left({\frac {1}{n^{2}}}A,a\right)\subseteq K\subseteq E(A,a)}$
• Dado un cuerpo convexo centralmente simétrico y bien delimitado (K; n, R, r) descrito por un oráculo WSEP, se puede encontrar un elipsoide E ( A , a ) tal que . Tenga en cuenta 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 politiempo. ${\displaystyle E\left({\frac {1}{n(n+1)}}A,a\right)\subseteq K\subseteq E(A,a)}$ ${\displaystyle 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 conjunto solución de un sistema de desigualdades lineales, se puede encontrar un elipsoide E ( A , a ) tal que . ${\displaystyle E\left({\frac {1}{(n+1)^{2}}}A,a\right)\subseteq K\subseteq E(A,a)}$
• Dado un cuerpo convexo centralmente simétrico y bien acotado (K; n, R, r) dado como conjunto solución de un sistema de desigualdades lineales, se puede encontrar un elipsoide E ( A , 0 ) tal que . ${\displaystyle 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 a la relación de N( x ) con la norma euclidiana. Entonces podemos calcular en tiempo polinómico de Oracle una transformación lineal T de R ⁿ tal que, para todo x en R ^norte ,.​ ${\displaystyle c_{1}\|x\|\leq N(x)}$ ${\displaystyle \|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 delimitado ( 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 contenga K , tal que . ${\displaystyle R^{*}\leq {\frac {1}{2}}{\sqrt {n}}\|x-y\|}$
• Dado un cuerpo convexo bien delimitado ( K ​​; n , R , r ) descrito por un oráculo WSEP, su ancho se puede aproximar encontrando dos hiperplanos paralelos c ^T x=d ₁ yc ^T x =d ₂ que se encuentran en dos lados de K , y una bola con radio r* contenida en K , tal que ${\displaystyle r^{*}={\frac {d_{2}-d_{1}}{2(n+1){\sqrt {n}}\|c\|}}}$

Algunos problemas aún no resueltos (a partir 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 en 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 politiempo utilizando oráculos WOPT para K y L. Lo mismo se aplica a WVIOL, WSEP y WVAL. Sin embargo, no ocurre lo mismo con 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 usando los respectivos oráculos para K y L.
• Para la intersección K ח L, puede ser imposible calcular el radio interior en politiempo, 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 politiempo utilizando los respectivos oráculos para K y L.
• Dados los oráculos WSEP para K y L, y un número racional r >0, es posible en tiempo polinómico de oráculo devolver (a) una afirmación de que la intersección K ח L contiene una bola con radio r , o (b) una 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 la intersección contiene una bola o hay un hiperplano que casi separa K de L.

De oráculos débiles a fuertes

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

Conjuntos convexos generales

Un algoritmo para WMEM, dado el radio circunscrito R y el radio inscrito r y el punto interior a ₀ , puede resolver el siguiente problema de membresía ligeramente más fuerte (aún más débil que SMEM): dado un vector y en Q ⁿ , y un ε racional >0, ya sea afirmar que y en S ( K,ε ), o 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 . Luego, se pueden utilizar muchos oráculos para problemas débiles para resolver los problemas fuertes correspondientes en tiempo oráculo-polinomial. Las reducciones requieren un límite superior en la complejidad de representación ( complejidad de faceta o complejidad de vértice ) del poliedro: ^{[1] : Sec. 6.3}

• Un oráculo para WNEMPT, para un poliedro P de dimensión completa 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é tan esencial es la información adicional para las reducciones anteriores? ^{[1] : 173}

• La suposición de que P es de dimensiones completas es esencial: si P no es de dimensiones completas, entonces la bola interior S( K , -ε ) está vacía. Por tanto, cualquier oráculo para resolver un problema débil no puede distinguir entre P y el conjunto vacío.
• El supuesto de que P es acotado puede flexibilizarse: es posible definir variantes de los problemas débiles para poliedros que pueden ser ilimitados y demostrar 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. Prueba : Supongamos que tenemos un poliedro P con una 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. Entonces es posible que P = H y la respuesta sea "sí", pero también es posible que P sea el casco convexo de todos los vértices distintos de cero de H y la respuesta sea "no". Por lo tanto, ningún algoritmo politime puede resolver SMEM.

Implicaciones de variantes fuertes

Utilizando los resultados anteriores, es posible probar implicaciones entre variantes fuertes. Se puede hacer lo siguiente en tiempo polinomial de Oracle para un poliedro bien descrito , un poliedro para el cual se conoce un límite superior en la complejidad de la 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 el 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 reemplazarse con 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 (= a vector c en R ⁿ tal que c ^T y > c ^T x para todo x en P ), pero si y está en P , aún puede devolver un hiperplano: un vector c en R ⁿ tal que c ^T y ≥ c ^T x para todo x en P .

Entonces SSEP, SVIOL y SOPT son todos equivalentes en tiempo polinomial. 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, también se puede encontrar una solución dual óptima básica en politiempo. ^{[1] : Thm.6.5.14}

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

No se pueden realizar otras reducciones sin información adicional:

• Si P no es de dimensiones completas, entonces SMEM no puede resolver SSEP, SVIOL o SOPT.
• Si P no está acotado, 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 requiere una garantía de que el conjunto convexo contenga al menos un punto (no necesariamente un vértice) con una longitud de representación acotada. Demuestra que, bajo este supuesto, SNEMPT se puede resolver (se puede encontrar un punto en el conjunto convexo) en politiempo. ^{[5] : Thm.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] : Thm.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 la 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 ^T x .
• Dados los vectores c ₁ , c ₂ , encuentre un vértice de P que maximice c ₁ ^T x y, sujeto a esto, maximice c ₂ ^T x ( maximización lexicográfica ).
• Encuentre el casco afín de P . ^[6] Esto también implica encontrar la dimensión de P y un punto en el interior relativo de P.
• Decida 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 ).

Ver 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

1. 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, señor  1261419
2. Yamnitsky, Boris; Levin, Leonid A. (1982). "Un antiguo algoritmo de programación lineal se ejecuta en tiempo polinómico". 23º Simposio Anual sobre Fundamentos de la Informática (SFCS 1982) . págs. 327–328. doi : 10.1109/SFCS.1982.63 . Consultado el 29 de enero de 2024 .
3. Suave, Robert G.; Goldfarb, Donald; Todd, Michael J. (diciembre de 1981). "Artículo destacado: el método elipsoide: una encuesta". La investigación de operaciones . 29 (6): 1039–1091. doi :10.1287/opre.29.6.1039. ISSN  0030-364X.
4. Yudin y Nemirovskii, 1976, https://elibrary.ru/item.asp?id=38308898 (en ruso)
5. Jain, Kamal (2007). "Un algoritmo de tiempo polinomial para calcular el equilibrio del mercado Arrow-Debreu para servicios públicos lineales". Revista SIAM de Computación . 37 (1): 303–318. doi :10.1137/S0097539705447384. ISSN  0097-5397.
6. Edmonds, J.; Polea en blanco, WR; Lovász, L. (1 de septiembre de 1982). "Descomposiciones de ladrillos y clasificación correspondiente de gráficos". Combinatoria . 2 (3): 247–274. doi :10.1007/BF02579233. ISSN  1439-6912. S2CID  37135635.