Me gustaría encontrar un algoritmo de tiempo polinómico que determine si el lapso de un conjunto dado de matrices contiene una matriz de permutación.
Si alguien sabe si este problema es de una clase de complejidad diferente, sería igual de útil.
EDITAR: He etiquetado esta pregunta con la Programación lineal, porque tengo una fuerte sospecha de que si existiera tal solución, sería una especie de algoritmo de programación lineal. La razón por la que creo esto es porque los puntos extremos del politopo de Birkhoff son precisamente las matrices de permutación. Si luego pudiera encontrar una función objetivo que se maximice o minimice solo en los vértices del politopo de Birkhoff, podría restringir su función a la intersección del politopo y su subespacio vectorial, luego maximizarla en tiempo polinómico. Si este valor fuera una matriz de permutación, sabría que el conjunto contiene una permutación. Esos son mis pensamientos sobre el tema.
EDITAR 2: Después de pensar un poco más, me parece que las matrices de permutación son precisamente los elementos del Politopo de Birkhoff con la norma euclidiana , consideramos que el politopo de Birkhoff es el casco convexo de los matrices de permutación. Quizás eso también podría ser significativo.
EDITAR 3: agregué la etiqueta de programación semidefinida, porque después de mi comentario anterior, estoy empezando a pensar que una solución de programación semidefinida puede ser posible ya que ahora es un algoritmo de optimización cuadrática con restricciones lineales.
Respuestas:
Por supuesto, se deduce que es poco probable que el problema tenga un algoritmo de poli-tiempo según lo solicitado por op.
Aquí está la intuición. El problema en la publicación es
Esto es esencialmente lo mismo que
Esto a su vez es lo mismo que
Reducir la suma de subconjuntos al último problema es un ejercicio estándar.
Aquí está la prueba detallada.
Defina el siguiente problema intermedio:
Probar esto es un ejercicio de tarea estándar. La prueba está al final.
Prueba de lema 2. Arregle una entrada de suma de coincidencias: un gráfico bipartito completo con pesos de bordes enteros no negativos w : U × V → N + , y objetivo T ∈ N + , donde U = { u 1 , ... , u n } y V = { v 1 , ... , v n } . Para cada yoG = ( U, V, E) w : U× V→ N+ T∈ N+ U= { u1, ... , unorte} V= { v1, ... , vnorte} , n + 1 = w ( u , defina M ( i j ) como la matriz en R ( n + 1 ) × ( n + 1 ) donde M ( i j ) i j = T , y M ( i j ) n + 1i , j ∈ { 1 , 2 , ... , n } METRO( i j ) R( n + 1 ) × ( n + 1 ) METRO( i j )yo j= T , y todas las demás entradas son cero. La reducción genera el siguiente conjunto de matrices:
{ M ( i j ) : i , j ∈ { 1 , ... , n } } .
Esto define la reducción.METRO( i j )n + 1 , n + 1= w ( uyo, vj)
Reclamación. El lapso de este conjunto de matrices consiste en aquellas matrices satisfacen las restricciones lineales M h , n + 1 = M n + 1 , h = 0 para todo h ≤ n y la restricción linealMETRO∈ R( n + 1 ) × ( n + 1 ) METROh , n + 1= Mn + 1 , h=0 h≤n
( Prueba de reclamación. Al inspeccionar cada matriz en el conjunto satisface estas restricciones, por lo que toda combinación lineal de esas matrices sí. Por el contrario, si M ∈ R ( n + 1 ) × ( n + 1 ) satisface las restricciones , entonces M es igual a la combinación lineal M ′ = ∑ n i = 1 ∑ n j = 1 α i j M ( i jM(ij) M∈R( n + 1 ) × ( n+1) M de las matrices, donde α i jM′=∑ni=1∑nj=1αyojM( i j ) . Tenga en cuenta en particular que, por las diversas definiciones y las restricciones lineales,
M ′ n + 1 , n + 1 = ∑ i j α i j w ( u i , v j i j w ( u i , v jαij=Mij/M(ij)ij=Mij/T
Esto prueba el reclamo).
Ahora mostramos que la reducción es correcta. Es decir, el gráfico dado tiene una coincidencia de peso T si y solo si el conjunto de matrices abarca una matriz de permutación.sol T
( Solo si ) . Primero suponga que la gráfica dada tiene una ponderación T perfecta que coincide con M ' . Supongamos que M ∈ { 0 , 1 } ( n + 1 ) × ( n + 1 ) sea la matriz de permutación n × n correspondiente , con una fila y columna adicionales agregadas de modo que M n + 1 , n + 1 = 1 y M h , n +sol T METRO′ METRO∈ { 0 , 1 }( n + 1 ) × ( n + 1 ) n × n METROn + 1 , n + 1= 1 , n + 1 =1para todoh≤n. Entonces ∑ n i = 1 ∑ n j = 1 M i j w( u i , v j )es el peso de M ′ , es decir,Ty M n + 1METROh , n + 1= Mn + 1 , h= 0 h ≤ n ∑nortei = 1∑nortej = 1METROyo jw ( uyo, vj) METRO′ T METROn + 1 , n + 1= 1 , Por lo que las restricciones lineales en la bodega de la reivindicación, y el lapso de la conjunto dado de matrices contiene la matriz de permutación .METRO
( Si. ) Por el contrario, supongamos que el lapso contiene cualquier matriz de permutación . Según la afirmación, la única entrada distinta de cero en la fila n + 1 o la columna n + 1 es M n + 1 , n + 1 , por lo que (como M es una matriz de permutación) debe ser que M n + 1 , n + 1 = 1 . Entonces, eliminar la última fila y columna da una matriz de permutación n × n . Deje que M ' sea la combinación perfecta deMETRO n + 1 n + 1 METROn + 1 , n + 1 METRO METROn + 1 , n + 1= 1 n × n METRO′ correspondiente a esamatriz de permutación n × n . El peso de M ' es Σ n i = 1 Σ n j = 1 M i j w ( u i , v j ) , que (por la demanda) es T M n + 1 , n + 1 = T . Entonces, el gráfico dado tiene unacoincidencia depeso- T , lo que demuestra el Lema 2 .sol n × n METRO′ ∑nortei = 1∑nortej = 1METROyo jw ( uyo, vj) TMETROn + 1 , n + 1= T T □
Aquí está la prueba retrasada de Lemma 1:
Prueba de lema 1. Dada la instancia de suma de subconjuntos , la reducción genera la instancia de suma de coincidencias ( G = ( U , V , E ) , T ) donde U = { u 1 , u 2 , ... , u 2 n } , V = { v 1 , v 2 ,( w , T) ∈ Nnorte+×N+ (G=(U,V,E),T) U={u1,u2,…,u2n} , para cada i ∈ { 1 , ... , n } , edge ( u i , v i )V={v1,v2,…,v2n} i ∈ { 1 , ... , n } ( uyo, vyo) tiene un peso , y todos los bordes restantes tienen un peso cero.wyo
Para cualquier coincidencia perfecta con pesos de aristas que sumen , el conjunto S = { i : ( u i , v i ) ∈ M , i ≤ n } es una solución para la instancia de Subset-Sum dada (ya que estos son los únicos no bordes de peso cero en M ).T S= { i : ( uyo, vyo) ∈ M, i ≤ n } METRO
Por el contrario, dada cualquier solución para la instancia de Subconjunto-Suma, diga con ∑ i ∈ S w i = T , el conjunto de aristas { ( u i , v i ) : i ∈ S } es una coincidencia parcial con el peso T , y se extiende fácilmente a una coincidencia perfecta de peso- T agregando, por ejemplo, el siguiente conjunto de bordes (peso cero):S⊆ { 1 , ... , n } ∑i ∈ Swyo= T { ( uyo, vyo) : i ∈ S} T T
Esto prueba el Lema 1. El teorema se desprende de los Lemas 1 y 2. □
ps Como un aparte, de acuerdo con esta respuesta , la restricción de Matching-Sum a instancias con pesos de borde polinomialmente limitados está en P. Pero estoy seguro de que la restricción del problema en la publicación a matrices con polinomialmente acotado (entero ) las entradas siguen siendo NP hard.
fuente
Con respecto al problema de calcular el diámetro de un politopo presentado como la intersección de medios espacios, el problema es NP-duro en general, y también NP-difícil de aproximar dentro de cualquier factor constante, vea el artículo de Brieden y las referencias en el mismo. Creo que para politopos simétricos centralmente, un SDP da unO ( logmetro-----√) aproximación donde metro es el número de desigualdades que definen el politopo. Bosquejo esto debajo de la línea.
En su caso, el politopo de BirkhoffPAGS no es centralmente simétrico, sino que funciona con el casco convexo de PAGS y - P es suficiente para sus propósitos. Creo que este politopo "Birkhoff simétrico" puede representarse como el conjunto de todas las matrices cuadradasMETRO que satisfacen:
Si esta es una representación correcta (no estoy seguro), puede agregar las restricciones que restringen este politopo a su subespacio dado. No es difícil adaptar el SDP debajo de la línea a esta representación, pero elijo no pasar por él para mantener la notación manejable.
No estoy seguro de qué diámetro aproximado hace para su problema: probablemente le permite decidir si el subespacio dado está cerca de una matriz de permutación o lejos de todos ellos, pero no he calculado los cálculos.
Permítanme terminar con un boceto del redondeo de SDP (que es una tarifa bastante estándar). DejarPAGS= { x : - b ≤ A x ≤ b } ser un politopo centralmente simétrico, donde UNA es m × n . Defina el programa vectorial:
sujeto a:
Sobre elvyo ir más allá norte -dimensionales vectores. Esto se puede escribir como un SDP en la forma estándar y es una relajación del diámetro dePAGS es decir α es al menos el diámetro euclidiano de PAGS .
Ahora afirmo queα ≤ O ( logmetro-----√) ⋅ diam ( P) . Para mostrar esto, te daré un algoritmo que, dado( vyo)nortei = 1 de valor α , salidas x ∈ P de longitud al menos αO ( logmetro√) . El algoritmo es solo una proyección aleatoria: elija una aleatorianorte vector tridimensional sol donde cada solyo Es un gaussiano estándar. ConjuntoX~yo= gTvyo . Por propiedades estándar de gaussianos:
Las dos ecuaciones ya implican que existe unX tal que x ∈ P y ∥ x ∥22≥ 1doIniciar sesiónmetro√α . O, usando límites de concentración, puede mostrar eso con probabilidad constante12 CIniciar sesiónmetro√X~∈ P y ∥ x~∥2≥ 12α .
fuente