Vi anser att det osplitterbara flödesproblemet på en linje. I detta problem får vi en uppsättning n uppgifter, var och en anges av en starttid s i, en sluttid t i, en efterfrågan d i > 0, och en vinst p i > 0. En uppgift, om accepterad, kräver d i enheter av "bandbredd" från tid s i till t i och tillfaller en vinst p i. För varje gång t, vi är också specificerade den tillgängliga bandbredd c t, och målet är att hitta en delmängd av uppgifter med maximal vinst som omfattas av bandbredd begränsningar. Vi presenterar den första polynom tid O (log n) approximation algoritm för detta problem. Detta ökar avsevärt den senaste tekniken, eftersom ingen polynom tid o(n) approximation var känd tidigare. Tidigare resultat för detta problem var kända endast i mer restriktiva miljöer; i synnerhet, antingen uppfyller instansen det så kallade "no-bottleneck" antagandet: max i d i ≤ min t c t, eller förhållandet mellan både högsta till lägsta krav och maximal till minsta kapacitet polynom (eller kvasi-polynomially) begränsas i n. Vårt resultat, å andra sidan, kräver inte dessa antaganden. Vår algoritm är baserad på en kombination av dynamisk programmering och avrundning en naturlig linjär programmering avkoppling för problemet. Även om det finns ett (n) integratitetsgap känt för denna LP-avslappning, är vår nyckelidé att utnyttja vissa strukturella egenskaper hos problemet för att visa att fall som är dåliga för LP faktiskt kan hanteras med hjälp av dynamisk programmering.
Detta resultat förbättrar på den tidigare mest kända polynom tid O (log n)-tillnärmning algoritm designad av Bansal et al. Hoppa över det.
A logarithmic approximation for unsplittable flow on line graphs
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}