Vi presenterar de första approximationssystemen för att minimera viktad flödestid på en enda maskin med företräde. Vårt första resultat är en algoritm som beräknar en (1+ )- ungefärlig lösning för alla fall av viktad flödestid i O(n O(ln W ln P/ 3 ) tid; här P är förhållandet mellan maximal jobbbearbetningstid till minimal jobbbearbetningstid, och W är förhållandet mellan maximal arbetsvikt och minimal arbetsvikt. Detta resultat ger direkt en kvasi-PTAS för viktad flödestid när P och W är polybundet, och en PTAS när de båda är O(1). Vi stärker det tidigare resultatet för att visa att för att få en kvasi-PTAS räcker det med att bara ha en av P och W att vara poly-bundet. Vårt resultat ger starka bevis för hypotesen att det viktade flödestidsproblemet har ett PTAS. Vi noterar att problemet är starkt NP-hård även när P och W är O(1). Vi betraktar därefter två viktiga specialfall av viktad flödestid, nämligen när P är O(1) och W är godtycklig, och när vikten av ett jobb är omvänd av sin bearbetningstid som kallas stretch metrisk. För båda de ovan nämnda specialfallen får vi en (1 + ) - approximation för alla > 0 genom att använda en randomiserad partitionering schema för att minska en godtycklig instans till flera fall som alla har P och W avgränsas av en konstant som endast beror på.
Chekuri och Khanna REF gav en kvasi-PTAS för detta problem, där körtiden var O(n O (logW logP ) ).
Approximation schemes for preemptive weighted flow time
{'venue': "STOC '02", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}