Abstrakt. I detta papper etablerar vi max-flöde min-cut teorem för flera viktiga klasser av multicommodity flödesproblem. I synnerhet visar vi att för n-node multicommodity flow problem med enhetliga krav, är det maximala flödet för problemet inom en O (log n) faktor av den övre gränsen underförstått av min-cut. Resultatet (som är existentiellt optimalt) etablerar en viktig analog av den berömda 1-commodity max-flow min-cut teorem för problem med flera varor. Resultatet har också betydande tillämpningar inom området approximationsalgoritmer. Till exempel använder vi flödesresultatet för att designa den första polynomtiden (polylog n-times-optimala) approximationsalgoritmer för välkända NP-hårda optimeringsproblem såsom grafpartitionering, min-cut linjärt arrangemang, korsningsnummer, VLSI layout, och minimal feedback båge set. Tillämpningar av flödesresultaten på ruttproblem, omkonfigurering av nätverk, kommunikation i distribuerade nätverk, vetenskaplig databehandling och snabb blandning av Markovkedjor beskrivs också i tidningen.
För allmänna problem med multimoditetsflöde beaktades approximationsalgoritmer i REF.
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}