Approximation schemes for preemptive weighted flow time

DOI10.1145/509907.509954MaRDI QIDQ3579232zbMATH OpenOpenAlexFDO

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

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)