Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time

DOI10.1137/19M1244512zbMath1479.90077arXiv1802.07439OpenAlexW3090692263MaRDI QIDQ5129231

Amit Kumar, Jatin Batra, Naveen Garg

Publication date: 26 October 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.07439

zbMATH Keywords

schedulingdynamic programmingmulticut

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Approximation algorithms for average stretch scheduling
• Weighted geometric set cover via quasi-uniform sampling
• On Capacitated Set Cover Problems
• On Column-Restricted and Priority Covering Integer Programs
• Approximation schemes for preemptive weighted flow time
• Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
• Speed is as powerful as clairvoyance
• Fair Scheduling via Iterative Quasi-Uniform Sampling
• Minimizing weighted flow time
• The Geometry of Scheduling
• Algorithms for minimizing weighted flow time
• A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
• A unified approach to approximating resource allocation and scheduling
• LATIN 2004: Theoretical Informatics

This page was built for publication: Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time