matriz de supnick

Una matriz de Supnick o matriz de Supnick (llamada así en honor a Fred Supnick del City College de Nueva York , quien introdujo la noción en 1957) es una matriz de Monge que también es una matriz simétrica .

Definición matemática

Una matriz de Supnick es una matriz de Monge cuadrada que es simétrica alrededor de la diagonal principal .

Una matriz de n por n es una matriz de Supnick si, para todo i , j , k , l tal que si

${\displaystyle 1\leq i<k\leq n}$y ${\displaystyle 1\leq j<l\leq n}$

entonces

${\displaystyle a_{ij}+a_{kl}\leq a_{il}+a_{kj}\,}$

y también

${\displaystyle a_{ij}=a_{ji}.\,}$

Rudolf y Woeginger dan una definición lógicamente equivalente, quienes en 1995 demostraron que

Una matriz es una matriz de Supnick si se puede escribir como la suma de una matriz suma S y una combinación lineal no negativa de matrices de bloques LL-UR.

La matriz suma se define en términos de una secuencia de n números reales {α _i }:

${\displaystyle S=[s_{ij}]=[\alpha _{i}+\alpha _{j}];\,}$

y una matriz de bloques LL-UR consta de dos rectángulos colocados simétricamente en las esquinas inferior izquierda y superior derecha para los cuales a _ij  = 1, con el resto de los elementos de la matriz iguales a cero.

Propiedades

La suma de dos matrices de Supnick dará como resultado una nueva matriz de Supnick (Deineko y Woeginger 2006).

Multiplicar una matriz de Supnick por un número real no negativo produce una nueva matriz de Supnick (Deineko y Woeginger 2006).

Si la matriz de distancias en el problema de un viajante puede escribirse como una matriz de Supnick, ese caso particular del problema admite una solución fácil (aunque el problema es, en general, NP difícil ).

Referencias

• Supnick, Fred (julio de 1957). "Líneas hamiltonianas extremas". Anales de Matemáticas . Segunda Serie. 66 (1): 179–201. doi :10.2307/1970124. JSTOR  1970124.
• Woeginger, Gerhard J. (junio de 2003). «Problemas computacionales sin Computación» (PDF) . Nieuwarchief . 5 (4): 140–147.
• Deineko, Vladimir G.; Woeginger, Gerhard J. (octubre de 2006). "Algunos problemas relacionados con los viajantes de comercio, los dardos y las monedas de euro" (PDF) . Boletín de la Asociación Europea de Informática Teórica . 90 . EATC : 43–52. ISSN  0252-9742.