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

DOI10.1137/19M1244512MaRDI QIDQ6139826OpenAlexFDO

Authors Jatin Batra, Naveen Garg, Amit Kumar

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

dynamic programmingschedulingmulticut

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 7051295 (Why is no real title available?)
• A polynomial time constant approximation for minimizing total weighted flow-time
• A unified approach to approximating resource allocation and scheduling
• Algorithms for minimizing weighted flow time
• Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
• Approximation algorithms for average stretch scheduling
• Approximation schemes for preemptive weighted flow time
• Fair scheduling via iterative quasi-uniform sampling
• LATIN 2004: Theoretical Informatics
• Minimizing weighted flow time
• On capacitated set cover problems
• On column-restricted and priority covering integer programs
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Speed is as powerful as clairvoyance
• The geometry of scheduling
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover via quasi-uniform sampling

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139826)