Complexidade da convolução no anel max / plus

10

Podemos fazer convolução em para mais / multiplicar polinômios com FFT. No entanto, a abordagem não parece muito generalizável para anéis em geral. Houve algum progresso na convolução ingênua de para o anel max / plus?O(nlogn)O(n2)

Devo observar que é possível transformar soft-max / plus em plus / product fazendo exponenciação. Aqui .soft-max(x,y)=log(ex+ey)=max(x,y)+log(1+emin(x,y)max(x,y))

Thomas Ahle
fonte
11
@ChaoXu comment -> answer?
Sasho Nikolov

Respostas:

11

Há uma pergunta mais geral sobre mathoverflow .

Pedi uma pergunta semelhante sobre CS.SE . O jbapple forneceu uma boa resposta. Citar

"Colares, convoluções e X + Y", de Bremner et al. mostra um para este problema na RAM real e umO(nO(n2(lglgn)3lg2n)algoritmo no modelo de árvore de decisão linear não uniforme.O(nn)

Qualquer melhoria nesse limite esclarecerá alguns problemas difíceis, como classificar e todos os pares de caminhos mais curtos.X+Y

Se uma das funções for convexa / côncava, podemos resolver o problema em . Veja "Acelerando a programação dinâmica", de Eppstein et al. .O(nregistron)

Chao Xu
fonte
11
Obrigado. Também gostei de ler sobre isso no link mathoverflow.
Thomas Ahle
Gostaria de saber se "aumentar monotonicamente" pode ser uma propriedade útil.
Thomas Ahle
2
O primeiro problema que os autores tentam resolver no artigo Colares está aumentando monotonicamente. É provável que não haja um algoritmo conhecido que tenha um desempenho melhor que o caso geral.
Chao Xu