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

DOI10.1137/19m1244512OpenAlexW3090692263MaRDI QIDQ6139826

Jatin Batra, Amit Kumar, Naveen Garg

Publication date: 19 December 2023

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

Full work available at URL: https://doi.org/10.1137/19m1244512

zbMATH Keywords

schedulingdynamic programmingmulticut

Mathematics Subject Classification ID

Approximation algorithms (68W25)

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