Vi studerar det klassiska problemet Node-Dis joint Paths (NDP): givet en n-vertex graf G och en samling M = {(s1, t1),. .., (s k, t k )} par av hörn av G kallas efterfrågan par, hitta en maximal-kardinalitet uppsättning node-olika vägar som förbinder efterfrågeparen. NDP är ett av de mest grundläggande routing problem, som har studerats i stor utsträckning. Trots detta finns det fortfarande stora luckor i vår förståelse av dess approximabilitet: den mest kända övre gränsen för O( ❌ n) för dess approximationsförhållande uppnås via en enkel girig algoritm, medan det bästa nuvarande negativa resultatet visar att problemet inte har en bättre än  och/eller log 1/2−δ n- approximation för alla konstanta δ, enligt standard komplexa antaganden. Även för planar grafer ingen bättre approximation algoritmer är kända, och så vitt vi vet, den bästa negativa gränsen är APX-hårdhet. Kanske det största hindret för att få bättre approximation algoritmer för NDP är att de flesta för närvarande kända approximationsalgoritmer för denna typ av problem förlitar sig på standard multicommodity flow relaxation, vars integrality gap är.( ε n) för NDP, även i plana grafer. I detta papper bryter vi barriären av O( ε n) om tillnärmningen av NDP i plana grafer och få en Õ(n 9/19 ) ungefärlig. Vi introducerar en ny linjär programmering av problemet, och ett antal nya tekniker, som vi hoppas kommer att vara till hjälp för att utforma mer kraftfulla algoritmer för detta och relaterade problem.
Därav Õ(n 9/19 )-tillnärmningsalgoritm för NDP med plana försörjningsdiagram REF innebär samma approximationsförhållande för EDP med G + H-planar.
Improved approximation for node-disjoint paths in planar graphs
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}