Matriz de Supnick

Una matriz de Supnick o arreglo de Supnick , que recibe su nombre de Fred Supnick del City College de Nueva York , quien introdujo el concepto en 1957 , es un arreglo de Monge que también es una matriz simétrica .

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

Una matriz n x 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 dieron una definición lógicamente equivalente y en 1995 demostraron que

Una matriz es una matriz de Supnick si y solo 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 todos los demás elementos de la matriz iguales a cero.

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

La multiplicación de 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 un problema del viajante de comercio se puede escribir como una matriz de Supnick, esa instancia particular del problema admite una solución fácil (aunque el problema sea, en general, NP difícil ).

• 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 vendedores ambulantes, dianas de dardos y monedas de euro" (PDF) . Boletín de la Asociación Europea de Ciencias de la Computación Teórica . 90. EATCS : 43–52 . ISSN 0252-9742 .