Algoritmos de Streaming para Floresta de Steiner Geométrica

Consideramos uma generalização do problema da árvore de Steiner, o problema da floresta de Steiner, no plano euclidiano: a entrada é um multiconjunto \ (XR^2\), partitionado em \ (k\) classes de cor \ (C₁, , C₊ X\). O objetivo é encontrar um grafo euclidiano de custo mínimo \ (G\) tal que cada classe de cor \ (C₈\) esteja conectada em \ (G\). Estudamos este problema da floresta de Steiner no contexto de streaming, onde o stream consiste em inserções e exclusões de pontos para \ (X\). Cada ponto de entrada \ (x X\) chega com sua cor \ (color (x) \), e como de costume para streams geométricos dinâmicos, a entrada é restrita à grade discreta \ (\1, , \^2\). Projetamos um algoritmo de streaming de passagem única que usa \ (poly (k) \) espaço e tempo, e estima o custo de uma solução ótima de floresta de Steiner dentro de uma razão arbitrariamente próxima da famosa razão de Steiner euclidiana \ (₂\) (atualmente \ (1. 1547₂ 1. 214\)). Esta garantia de aproximação se iguala ao limite de ponta para a árvore de Steiner em streaming, ou seja, quando \ (k=1\), e é uma grande questão em aberto melhorar a razão para \ (1+\) mesmo para este caso especial. Nossa abordagem se baseia em uma nova combinação de técnicas de streaming, como amostragem e esboço linear, com a estrutura clássica de programação dinâmica estilo Arora para problemas de otimização geométrica, que geralmente exige grande memória e até agora não foi aplicada no contexto de streaming. Complementamos nosso algoritmo de streaming para o problema da floresta de Steiner com argumentos simples que mostram que qualquer aproximação multiplicativa finita requer \ ( (k) \) bits de espaço.