Approximation schemes for preemptive weighted flow time

DOI10.1145/509907.509954zbMath1192.68877OpenAlexW2166867051MaRDI QIDQ3579232

Sanjeev Khanna, Chandra Chekuri

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://repository.upenn.edu/cgi/viewcontent.cgi?article=1072&context=cis_papers

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (13)

Minimizing the stretch when scheduling flows of divisible requests ⋮ Online weighted flow time and deadline scheduling ⋮ Scheduling and fixed-parameter tractability ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time ⋮ Fair Scheduling via Iterative Quasi-Uniform Sampling ⋮ Fixed-Parameter Approximation Schemes for Weighted Flowtime. ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ Minimizing flow time on a constant number of machines with preemption ⋮ Non-clairvoyant scheduling for weighted flow time ⋮ Minimizing Average Flow-Time ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time

This page was built for publication: Approximation schemes for preemptive weighted flow time