Approximation schemes for preemptive weighted flow time

DOI10.1145/509907.509954zbMATH Open1192.68877OpenAlexW2166867051MaRDI QIDQ3579232FDOQ3579232

Authors: Chandra Chekuri, Sanjeev Khanna 

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)

Cited In (15)

• Minimizing Average Flow-Time
• How unsplittable-flow-covering helps scheduling with job-dependent cost functions
• Designing PTASs for MIN-SUM scheduling problems
• Minimizing the stretch when scheduling flows of divisible requests
• Non-clairvoyant scheduling for weighted flow time
• Minimizing flow time on a constant number of machines with preemption
• Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
• Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings
• Fair scheduling via iterative quasi-uniform sampling
• Scheduling and fixed-parameter tractability
• Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time
• Online weighted flow time and deadline scheduling
• A PTAS for minimizing weighted flow time on a single machine
• Fixed-parameter approximation schemes for weighted flowtime
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579232)