Vi presenterar förbättrade approximationsalgoritmer för riktad multicut och riktad glesaste cut. Det nuvarande mest kända approximationsförhållandet för dessa problem är O(n 1/2 ). Vi får en Õ(n 11/23 )-uppskattning. Vår algoritm arbetar med den naturliga LP-avslappning som används i tidigare arbete. Vi använder en randomiserad avrundningsalgoritm med ett mer sofistikerat laddningssystem och analys för att uppnå vår förbättring. Detta innebär också aÕ(n 11/23 ) övre gräns på förhållandet mellan det maximala multimoditetsflödet och minsta multicut i riktade grafer.
Med multicut-lösningen använder MIA approximeringsalgoritmen O(n 11/23 ) som föreslagits av Agarwal et al. Hoppa över det.
Improved approximation for directed cut problems
{'venue': "STOC '07", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}