Aplicaciones de combinatoria aditiva en diseño de algoritmos

12

Estoy leyendo encuestas de Trevisan y Lovett sobre aplicaciones de aditivo combinatorio en TCS. La mayoría de estas aplicaciones caen bajo la complejidad computacional , por ejemplo, límites inferiores. Me pregunto si la combinatoria aditiva también ha encontrado aplicaciones en el diseño de algoritmos .

La motivación para mi pregunta es la siguiente: si bien la conexión entre la combinatoria aditiva y la complejidad parece algo natural, tengo curiosidad por ver cómo la estructura algebraica descubierta por la combinatoria aditiva podría explotarse en el diseño de algoritmos eficientes, si los hay. Apuntes a la literatura serían apreciados.

ds.algorithms reference-request co.combinatorics usuario32373
fuente

Creo que la "aceptación" de este tipo de preguntas no tiene sentido, ya que el objetivo es compilar una lista de indicadores relevantes. Pero acepté el de Ryan, ya que el resultado referenciado es definitivamente el tipo de conexiones que estaba buscando: el uso de la combinatoria aditiva es explícito en el diseño del algoritmo, y la resolución es intrigante porque BSG no logró descifrar el infame 3SUM.

user32373

17

Timothy Chan y Moshe Lewenstein tienen un artículo sobre 3SUM y problemas relacionados en el próximo STOC, que aplica una versión efectiva del teorema BSG de la combinatoria aditiva para resolver variantes de 3SUM más rápido que n ^ 2 veces.

Vea este enlace a los documentos de Chan .

Ryan Williams
fuente

3 S A T

$3SAT$

1

3 S A T

$3SAT$

3 S A T

$3SAT$

{1.308}^{n}

$1.308^n$

8

El algoritmo DC3 para calcular una matriz de sufijos aprovecha la combinatoria aditiva. Utiliza cubiertas de diferencia en una parte clave del algoritmo. Las ideas son muy interesantes y accesibles. El algoritmo también tiene un excelente rendimiento en la práctica y se enseña ampliamente.

$G$ $S$ $g \in G$ $s,t \in S$ $g=s-t$ $G$ $n$

Aquí está la cita:

Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt. Construcción de matriz de sufijo de trabajo lineal . Revista de la ACM, 2006.

DW
fuente

8

$B$ $n$ $O(2^{0.3399n}B^4)$

Ver Austrin, P., Kaski, P., Koivisto, M. y Nederlof, J. (2015, febrero). Subconjunto Suma en ausencia de concentración. En EW Mayr, y N. Ollinger (Eds.), 32º Simposio internacional sobre aspectos teóricos de la informática (STACS 2015) (Vol. 30, pp. 48-61).

Juho
fuente

5

Si incluye pruebas en el diseño de algoritmos, Samorodnitsky usa combinatoria aditiva para mostrar que las transformaciones lineales son comprobables de manera eficiente [aquí] .

Manu
fuente

3

Otro ejemplo es el trabajo clásico de Coppersmith y Winorgrad de 1990 sobre la multiplicación de matrices, que se basa en la combinatoria aditiva.

http://www.sciencedirect.com/science/article/pii/S0747717108800132

Shachar Lovett
fuente

Aplicaciones de combinatoria aditiva en diseño de algoritmos

Respuestas: