Generando un punto en un politopo racional

8

Considere un politopo racional que se define por medio de un oráculo de separación. Es decir, puede describirse implícitamente como , pero dado que es muy grande, utilizamos un oráculo, que da un punto , o bien dice o devuelve una media-espacio tal que .P P = { x R k : A x b , A Z m × k , b Z m } m x R k x P x SPPP={xRk:Axb,AZm×k,bZm}mxRkxPxS

Mi objetivo es encontrar un punto en o determinar que está vacío. Mi objetivo para un polinomio de tiempo de ejecución en el tamaño de representación de y , donde es el valor absoluto más grande de . Es decir, el algoritmo solo debe hacer muchas llamadas polinómicas al oráculo de separación.P U k U APPUkUA

En general, podría estar contenido en un hiperplano de dimensión inferior y, por lo tanto, es problemático utilizar el método elipsoide. Así, como en el truco de Khachiyan, me alter (y el oráculo de separación) para utilizar , en donde es algo así como . Intuitivamente, los medios espacios que definen son los mismos que los que definen solo que son traducidos por . El politopo tiene las siguientes propiedades: está vacío si está vacío, y si no está vacío,P P ϵ ϵ 1 / U P ϵ PPPPϵϵ1/UPϵPϵPϵPϵPPPϵ Es de dimensiones completas.

Mi pregunta es la siguiente: suponga que el algoritmo encuentra un punto . ¿Es posible generar un punto en usando ?pPϵPp

Chico
fuente

Respuestas:

8

De cualquier elección de un politopo en R k , ε , y un punto Q en R k es posible encontrar un politopo P en R k + 1 , junto con una incrustación de R k en R k + 1 , de manera que P está dentro de ε distancia Hausdorff de (la imagen incrustada de) P y tal que (la imagen incrustada de) q pertenece a P εPRkϵqRkP^Rk+1RkRk+1P^ϵPqP^ϵ. Para ello, simplemente hacen las facetas de P ser casi paralelos a la imagen incrustada de R k , de modo que su traducción por ε en R k + 1 provoca su intersección con R k a alejarse de P por una distancia mayor mucho .P^RkϵRk+1RkP^

Debido a que era arbitrario, el conocimiento de q no sirve para encontrar un punto dentro o cerca de P ; todo lo que podrías hacer con él, podrías hacerlo sin él. Sin embargo, debido a P y P son tan cerca, encontrar un punto cercano a P es equivalente a encontrar un punto cercano a P . Por lo tanto, el conocimiento de q (un punto en P ε ) no es de utilidad en la búsqueda de un punto cerca de P .qqPP^PPP^qP^ϵP^

David Eppstein
fuente
¡Gracias! Agregué una suposición de que el politopo es racional, así que (con suerte) ahora, hay esperanza de encontrar un punto en P.
Guy
Esa restricción no ayuda; que es fácil de hacer P racional en la construcción de David. P^
Jeff el
Supongo que el interrogador realmente pregunta cómo encontrar un punto cuando P no es dimensional completo. pPP
Chandra Chekuri
2

Si su objetivo es encontrar un punto en o determinar que P está vacío, ¿por qué no hace lo siguiente?PP

Sea un conjunto de medios espacios, inicialmente vacíos.H

Sea un punto, inicialmente igual a 0 k .x0k

  1. Dale al oráculo.x

  2. Si el oráculo dijo , lo has hecho.xP

  3. De lo contrario, sea el medio espacio violado devuelto por el oráculo. Vamos y la proyección ortogonal de x en S . SyxS

    • Si existe al menos una tal que y T , entonces lo has hecho: P está vacío.THyTP
    • De lo contrario, configure , y establezca x : = y . H:=H{S}x:=y
  4. Regrese a 1.

Giorgio Camerani
fuente
Gracias por la respuesta. Creo que va a trabajar, pero, a menos que me falta algo, el tiempo de ejecución será porportional a , el número de medias espacios que definen P . Estoy esperando un tiempo de ejecución que es polinomio en k y la representación de T , que es el valor absoluto más grande de A . Es decir, solo polinomio muchas llamadas al oráculo. mPkUA
Chico
¡De nada! ¿Está seguro de que tal requisito sobre el tiempo de ejecución es evidente al leer la pregunta?
Giorgio Camerani
1
Tienes razón. Lo agregaré
Chico