Approximating weighted completion time via stronger negative correlation

DOI10.1007/S10951-023-00780-YMaRDI QIDQ6620463zbMATH OpenFDO

Authors Alok Baveja, Xiaoran Qu, Aravind Srinivasan

Publication date 16 October 2024

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10951-023-00780-Y

zbMATH Keywords

approximation algorithmscompletion timedependent roundingscheduling

Mathematics Subject Classification ID

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

Recommendations

• Unrelated machine scheduling of jobs with uniform Smith ratios
• A unified approach to scheduling on unrelated parallel machines
• Scheduling Unrelated Machines by Randomized Rounding

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A new approximation technique for resource-allocation problems
• A PTAS for minimizing the weighted sum of job completion times on parallel machines
• A unified approach to scheduling on unrelated parallel machines
• An approximation algorithm for the generalized assignment problem
• Computing and software science. State of the art and perspectives
• Convex quadratic and semidefinite programming relaxations in scheduling
• scientific article; zbMATH DE number 1305540 (Why is no real title available?)
• scientific article; zbMATH DE number 1754639 (Why is no real title available?)
• Minimizing average completion time in the presence of release dates
• Non-approximability results for scheduling problems with minsum criteria
• On a generalization of iterated and randomized rounding
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
• Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution

Cited in

(1)

• An efficient polynomial time approximation scheme for minimizing the total weighted completion time on uniformly related machines

This page was built for publication: Approximating weighted completion time via stronger negative correlation

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