Esquemas de aproximação mais rápidos para problemas de fluxo multicommoditários fracionários

Apresentamos esquemas de aproximação totalmente polinomiais para problemas de fluxo multicommoditários concorrentes que operam em tempo de dependências mínimas possíveis em relação ao número de commodities k. Mostramos que, ao modificar os algoritmos de Garg e Könemann 1998 e Fleischer 2000, podemos reduzir seu tempo de execução em um grafo com n vértices e m arestas de Õ (ε −2 ( m 2 + km )) para Õ (ε −2 m 2 ) para uma representação implícita da saída, ou Õ (ε −2 ( m 2 + kn) para uma representação explícita, onde Õ ( f ) denota uma quantidade que é O ( f log O (1) m ). A representação implícita consiste em um conjunto de árvores enraizadas em fontes (podendo haver mais de uma árvore por fonte) e com sumidouros como suas folhas, juntamente com valores de fluxo para o fluxo direcionado da fonte para os sumidouros em uma árvore particular. Dada essa representação implícita, o valor aproximado do fluxo concorrente é conhecido, mas se quisermos o fluxo explícito por commodity por aresta, teremos que combinar todas essas árvores, e o custo para fazê-lo pode ser proibitivo. Caso queiramos calcular explicitamente o fluxo da solução, modificamos nossos esquemas para que operem em tempo polilogarítmico em nk (n é o número de nós na rede). Isso está dentro de um fator polilogarítmico do limite inferior trivial de tempo Ω( nk ) necessário para escrever explicitamente um fluxo multicommoditário de k commodities em uma rede de n nós. Portanto, nossos esquemas estão dentro de um fator polilogarítmico das dependências mínimas possíveis do tempo de execução em relação ao número de commodities k.