Vi anser att maximeringsversionen av kant-söndrat vägproblem (EDP). I oriktade grafer och riktade acykliska grafer får vi en övre gräns på approximationsförhållandet där n är antalet noder i grafen. Vi visar detta genom att etablera den övre gränsen på integrality gapet av den naturliga avkopplingen baserat på multicommodity flöden. Våra övre bundna matchningar inom en konstant faktor en lägre gräns av  och som är känd för både oriktade och riktade acykliska grafer. De bästa tidigare övre gränserna på integralititetsluckorna var O(min {n 2/3, ε m}) för oriktade grafer och O(min{ ε n log n, ε m} för riktade acykliska grafer; här m är antalet kanter i grafen. Dessa gränser är också de mest kända approximationskvoterna för dessa problem. Vårt band sträcker sig också till det ospliterbara flödesproblemet (UFP) när den maximala efterfrågan är som mest den minsta kapaciteten.
Den mest kända approximationsgarantin är O( ε n) REF, även när G är planar.
An O( √ n) approximation and integrality gap for disjoint paths and unsplittable flow
{'venue': 'Theory of Computing', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}