Discrepancia de permutaciones

La discrepancia de permutaciones es un subcampo de la teoría de la discrepancia que se ocupa de equilibrar los intervalos inducidos por las permutaciones de elementos. Existe un conjunto de n elementos y m permutaciones diferentes sobre este conjunto. La pregunta general de investigación es: ¿podemos colorear cada elemento con uno de dos colores diferentes (por ejemplo, blanco y negro), de manera que en cada permutación, cada intervalo contenga aproximadamente la misma cantidad de elementos de cada color?

Formalmente, la discrepancia de un intervalo se define como la diferencia entre el número de elementos blancos y el número de elementos negros en ese intervalo; el objetivo es colorear los elementos de tal manera que la discrepancia máxima de un intervalo en cada una de las permutaciones sea lo más pequeña posible.

Sean p ₁ , ..., p _m permutaciones de [ n ]. El conjunto de intervalos de una permutación es el conjunto de todos los subconjuntos de [ n ] que son adyacentes entre sí en la permutación. Por ejemplo, si n = 4 y una de las permutaciones es (1,2,3,4), entonces su conjunto de intervalos contiene, por ejemplo, las aristas (1,2), (1,2,3), (2,3), (2,3,4), etc.

La discrepancia de las permutaciones p ₁ , ..., p _m es el mínimo, sobre todas las coloraciones blanco-negro de los enteros en [ n ], del máximo sobre todos los intervalos, de la diferencia entre el número de enteros blancos y negros en el intervalo. ^{[ 1 ]}

• Cuando solo hay una permutación, es posible una discrepancia de 1, simplemente coloreando los enteros alternativamente de blanco a negro, de blanco a negro, etc.
• Cuando hay dos permutaciones, es posible una discrepancia de 2; esto fue demostrado por Spencer en 1987. ^{[ 1 ]}
• Para cualesquiera m permutaciones, la discrepancia es como máximo${\displaystyle 8m\log {n}}$y dicha coloración se puede calcular de manera eficiente. ^{[ 2 ]}
• Para cualesquiera tres permutaciones, Beck conjeturó que la discrepancia es constante. Sin embargo, esta conjetura fue refutada: para cualquier n que sea una potencia de 3, existen 3 permutaciones cuya discrepancia es${\displaystyle \lceil (\log _{3}{n})/3+1\rceil }$. Más precisamente, para cualquier coloración {1,-1}, si la suma de todos los colores es d , entonces existe algún entero q tal que, en las tres permutaciones, la suma de los primeros q colores es como máximo${\displaystyle (-\log _{3}{n}+2d-2)/3}$. ^{[ 3 ] : Cor.2} Esto tiene implicaciones para el problema de empaquetamiento de contenedores .

Jiang, Kulkarni y Singla ^{[ 1 ]} estudian el entorno en línea con llegada estocástica de puntos y demuestran que:

• Una coloración aleatoria produce una discrepancia esperada de${\displaystyle {\tilde {O}}({\sqrt {n}})}$.
• Existe un algoritmo eficiente que garantiza${\displaystyle O(n^{c/\log {\log {n}}})}$discrepancia, para alguna constante universal c, con alta probabilidad . Muestran una aplicación de este resultado a la división justa en línea .

A veces, los elementos no están disponibles con antelación, sino que llegan uno a uno, y cada elemento debe colorearse inmediatamente al llegar. Esta configuración en línea es un desafío incluso para una sola permutación. Jiang, Kulkarni y Singla denominan a la configuración con una permutación Discrepancia de intervalo en línea. Demuestran que: ^{[ 1 ] : Sec.3.2}

• Ningún algoritmo en línea puede garantizar una discrepancia constante.
• La coloración aleatoria da${\displaystyle {\tilde {O}}({\sqrt {n}})}$discrepancia esperada.
• Si la llegada es adversaria, la discrepancia de cualquier algoritmo en línea es${\displaystyle \Omega ({\sqrt {n}})}$.
• Si la llegada es estocástica, existe un algoritmo eficiente que lo garantiza.${\displaystyle O(n^{c/\log {\log {n}}})}$discrepancia, para alguna constante universal c, con alta probabilidad (es decir, con probabilidad 1-1/poly( n ), donde el exponente del polinomio depende de c ).

La demostración se extiende al caso de dos permutaciones, a las que denominan Discrepancia de Franja en Línea.

Los resultados de la discrepancia de permutaciones se han utilizado en el cálculo de subconjuntos aceptables , así como en la división justa en línea . ^{[ 1 ]}