Esta é uma pergunta um tanto subjetiva. Estou interessado em estudar a literatura sobre resultados de corte de fluxo multicomodidade, especialmente os resultados "positivos" que mostram que o fluxo é uma boa aproximação ao corte (por exemplo, dentro de um fator constante ou polilogarítmico no número de fluxos). Exemplos são:
1) O politopo do fluxo (também chamado de politopo da demanda) para o fluxo multicomodidade em gráficos não direcionados está dentro de O (log k) do corte, conforme mostrado em
F. Leighton e S. Rao, "Um teorema min-cut aproximado do fluxo máximo para problemas uniformes de fluxo multicomodidade com aplicações em algoritmos de aproximação", em Proc. do 28º Simpósio Anual de Fundamentos da Ciência da Computação, (Los Alamitos, Califórnia), 1988.
N. Linial, E. London e Y. Rabinovich, "A geometria dos gráficos e algumas de suas aplicações algorítmicas", Combinatorica, vol. 15, n. 2, pp. 215-245, 1995.
2) O pólipo de demanda do fluxo multicomoditário em gráficos direcionados com demandas simétricas está dentro de O (log ^ 2 k) do corte, como mostrado em
P. Klein, S. Plotkin, S. Rao e E. Tardos, "Limites na razão min-cut max-flow para fluxos diretos de multicomodidades", J. Algorithms, no. 22, pp. 241-269, 1997.
3) A soma máxima da taxa de transmissão em grupo está dentro de um fator 2 do multicut. (Não conheço uma referência para esse resultado. Alguém poderia me ajudar com isso? Obrigado.)
Eu gostaria de conhecer mais resultados positivos afirmando que o fluxo está próximo do corte, assumindo certa estrutura do problema (como a falta de direcionamento do gráfico ou demandas simétricas, como acima). Seria ótimo se você pudesse me dar um resumo de uma linha do (s) resultado (s) e uma referência do artigo. Obrigado.
fonte