@Article{QueyranneSchulz:06:Approximation-Bounds,
Author = {Queyranne, Maurice and Schulz, Andreas S.},
Journal = {SIAM Journal on Computing},
Title = {Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems},
Year = {2006},
Volume = {35},
Number = {5},
Pages = {1241--1253},
Doi = {10.1137/S0097539799358094},
Month = jan,
Annote = {$P|r_j;prec|\sum w_jC_j$ has a polynomial-time $4$-approximation.},
}
@Article{SittersYang:17:A-2+epsilon-approximation,
Author = {Ren\'e Sitters and Liya Yang},
Journal = {Operations Research Letters},
Title = {A $(2 + \epsilon )$-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective},
Year = {2018},
Volume = {46},
Number = {4},
Month = {jul},
Pages = {438--442},
Issn = {0167-6377},
Doi = {10.1016/j.orl.2018.05.007},
Eprint = {1706.07604},
Eprintclass = {cs.DS},
Eprinttype = {arXiv},
Keywords = {cs.DS, math.OC},
Publisher = {Elsevier {BV}},
Month = jul,
Annote = {$1|r_j;prec|\sum w_jC_j$ has a polynomial-time $(2+\epsilon)-approximation.}
}
@Article{HallSchulz:97:Scheduling-to-minimize,
Author = {Leslie A. Hall and Andreas S. Schulz and David B. Shmoys and Joel Wein},
Journal = {Mathematics of Operations Research},
Pages = {513---544},
Title = {Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms},
Volume = {22},
Year = {1997},
Publisher = {{INFORMS}},
Volume = {22},
Number = {3},
Doi = {10.1287/moor.22.3.513},
Month = aug,
Annote = {$1|prec|\sum w_jC_j$ has a polynomial time $2$-approximation, by solving a linear program (LP) and doing list scheduling in order of completion times in the LP solution,\\
$1|r_j;prec;pmtn|\sum w_jC_j$ has a polynomial time $2$-approximation, by solving a linear program (LP) and doing preemptive list scheduling in order of completion times in the LP solution,\\
$P|r_j;prec;pmtn|\sum w_jC_j$ has a polynomial-time $3$-approximation.}
}
@article{Li:20:Scheduling-to-minimize,
Author = {Li, Shi},
Title = {Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations},
Journal = {SIAM Journal on Computing},
Year = {2020},
Volume = {49},
Number = {4},
Pages = {FOCS17-409--FOCS17-440},
Doi = {10.1137/17M1156332},
Eprint = {1707.08039},
Eprintclass = {cs.DS},
Eprinttype = {arXiv},
Annote = {$P|prec|\sum w_jC_j$ has a polynomial-time $(2+2\ln 2+\epsilon)$-approximation,\\
$P|prec;p_j=1|\sum w_jC_j$ has a polynomial-time $(1+\sqrt 2)$-approximation,\\
$Q|prec|\sum w_jC_j$ has a polynomial-time $O(\log m/\log\log m)$-approximation.},
}
@Inproceedings{GargKulkarni:19:Lift-and-project,
Author = {Shashwat Garg and Janardhan Kulkarni and Shi Li},
Title = {Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time},
Booktitle = {Proceedings of the 2019 Annual {ACM-SIAM} Symposium on Discrete Algorithms},
Year = {2019},
Month = jan,
Eventtitle= {{SODA} 2019},
Publisher = {Society for Industrial and Applied Mathematics},
Pages = {1570--1584},
Doi = {10.1137/1.9781611975482.95},
Month = jan,
Annote = {$Pm|prec;p_j=1|\sum w_jC_j$ has a polynomial-time $(2+\epsilon)$-approximation.}
}
@Article{Jaeger:18:Approximating-total-weighted,
author = {Sven Jäger},
title = {Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates},
doi = {10.1016/j.orl.2018.07.006},
issn = {0167-6377},
number = {5},
pages = {505--509},
volume = {46},
journal = {Operations Research Letters},
publisher = {Elsevier {BV}},
year = {2018},
month = sep,
annote = {$P|r_j;prec|\sum w_jC_j$ has a polynomial-time $(2+2\ln 2+\epsilon)$-approximation.}
}
@InProceedings{ChekuriKhanna:01:A+PTAS+for+Minimizing,
author = {Chekuri, Chandra and Khanna, Sanjeev},
editor = {Orejas, Fernando and Spirakis, Paul G. and van Leeuwen, Jan},
title = {A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines},
booktitle = {Automata, Languages and Programming},
year = {2001},
publisher = {Springer},
pages = {848--861},
isbn = {978-3-540-48224-6},
doi = {10.1007/3-540-48224-5_69},
annote = {$Q||\sum w_jC_j$ has a polynomial-time approximation scheme.},
}
@inProceedings{ImShadloo:20:Weighted+Completion,
author = {Sungjin Im and Maryam Shadloo},
title = {Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution},
booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms},
eventtitle = {{SODA} 2020},
pages = {2790--2809},
doi = {10.1137/1.9781611975994.170},
publisher = {Society for Industrial and Applied Mathematics},
month = jan,
eprint = {2001.05015},
eprinttype = {arXiv},
eprintclass= {cs.DS},
annote = {$R||\sum w_jC_j$ has a polynomial-time $1.488$-approximation.},
}
@InProceedings{BazziNorouzi-Fard:15:Towards+Tight,
author = {Bazzi, Abbas and Norouzi-Fard, Ashkan},
editor = {Bansal, Nikhil and Finocchi, Irene},
title = {Towards Tight Lower Bounds for Scheduling Problems},
booktitle = {Algorithms -- ESA 2015},
year = {2015},
month = sep,
publisher = {Springer},
pages = {118--129},
isbn = {978-3-662-48350-3},
eprint = {1507.01906},
eprinttype = {arXiv},
eprintclass= {cs.CC},
annote = {$Q|prec|\sum w_jC_j$ has no constant approximation ratio if a structural hardness result for $k$-partite graphs is true.},
}
@InProceedings{KulkarniLi:2018:Flow-time+Optimization,
author = {Janardhan Kulkarni and Shi Li},
title = {Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
eventtitle= {APPROX/RANDOM 2018},
pages = {16:1--16:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-085-9},
ISSN = {1868-8969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.16},
eprint = {1807.02553},
eprinttype= {arXiv},
eprintclass= {cs.DS},
annote = {$1|r_j;prec;pmtn|\sum F_j$ has approximation ratio $\ge n^{\frac{1}{(\log\log n)^c}}$ for some $c > 0$ under ETH,\\
$1|r_j;prec;pmtn|\sum w_jF_j$ has an $O(1)$-approximation with $O(1)$ speed augmentation.},
}
@Article{Skutella:01:Convex+Quadratic,
author = {Skutella, Martin},
year = {2001},
month = mar,
journal = {Journal of the ACM},
title = {Convex Quadratic and Semidefinite Programming Relaxations in Scheduling},
doi = {10.1145/375827.375840},
issn = {0004-5411},
number = {2},
pages = {206--242},
volume = {48},
publisher = {{ACM}},
annote = {$R|r_j;pmtn|\sum w_jC_j$ has a $3$-approximation algorithm when migration is allowed.},
}