Algorithms for minimizing weighted flow time

DOI10.1145/380752.380778zbMath1323.90019OpenAlexW2086365412MaRDI QIDQ5175956

An Zhu, Sanjeev Khanna, Chandra Chekuri

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third 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=1069&context=cis_papers

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (26)

Lower bounds for on-line single-machine scheduling. ⋮ Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine ⋮ An Optimal Control Framework for Online Job Scheduling with General Cost Functions ⋮ Online weighted flow time and deadline scheduling ⋮ Approximating total flow time on parallel machines ⋮ Improved lower bounds for online scheduling to minimize total stretch ⋮ Joint replenishment meets scheduling ⋮ Scheduling and fixed-parameter tractability ⋮ A best possible online algorithm for minimizing the total completion time and the total soft penalty cost ⋮ Improved multi-processor scheduling for flow time and energy ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time ⋮ Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines ⋮ Fixed-Parameter Approximation Schemes for Weighted Flowtime. ⋮ Greedy multiprocessor server scheduling ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ Two-Agent Scheduling with Resource Augmentation on Multiple Machines ⋮ A PTAS for minimizing weighted flow time on a single machine ⋮ New resource augmentation analysis of the total stretch of srpt and SJF in multiprocessor scheduling ⋮ Non-clairvoyant scheduling for weighted flow time ⋮ From Preemptive to Non-preemptive Scheduling Using Rejections ⋮ Minimizing Average Flow-Time ⋮ Non-clairvoyantly scheduling to minimize convex functions ⋮ An optimal online algorithm for single-processor scheduling problem with learning effect ⋮ Unnamed Item ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Algorithms for minimizing weighted flow time