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

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

Cited in

(17)

• Non-clairvoyant scheduling for weighted flow time
• How unsplittable-flow-covering helps scheduling with job-dependent cost functions
• Minimizing flow time on a constant number of machines with preemption
• Designing PTASs for MIN-SUM scheduling problems
• Fair scheduling via iterative quasi-uniform sampling
• Minimizing Average Flow-Time
• Fixed-parameter approximation schemes for weighted flowtime
• 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
• 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
• Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings
• A flow shop scheduling problem with machine-dependent speeds: an ensemble approach with worst-case analysis
• Minimizing weighted flow time
• Minimizing the stretch when scheduling flows of divisible requests
• Online weighted flow time and deadline scheduling
• Scheduling and fixed-parameter tractability

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)