%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Christoph Durr at 2016-02-22 11:10:37 +0100
%% Saved with string encoding Occidental (Windows Latin 1)
@article{WilliamsonHall:97:Short-shop,
Author = {Williamson, DP and Hall, LA and Hoogeveen, JA and Hurkens, CAJ and Lenstra, Jan Karel and Sevast'Janov, SV and Shmoys, DB},
Date-Added = {2016-02-22 10:07:00 +0000},
Date-Modified = {2016-02-22 10:08:04 +0000},
Journal = {Operations Research},
Number = {2},
Pages = {288--294},
Publisher = {INFORMS},
Title = {Short shop schedules},
Volume = {45},
Year = {1997},
Annote = {$O||C_{\max}$ has polynomial time approximation ratio $\geq 5/4$\\
$F||C_{\max}$ has polynomial time approximation ratio $\geq 5/4$.
}}
@article{HoogeveenLenstra:94:Three-four,
Author = {Hoogeveen, JA and Lenstra, Jan Karel and Veltman, Bart},
Date-Added = {2016-02-22 10:00:04 +0000},
Date-Modified = {2016-02-22 10:00:12 +0000},
Journal = {Operations Research Letters},
Number = {3},
Pages = {129--137},
Publisher = {Elsevier},
Title = {Three, four, five, six, or the complexity of scheduling with communication delays},
Volume = {16},
Year = {1994},
Annote = {$P|prec;l=1;p_j=1|C_{\max}$ polynomial time approximation ratio is $\geq 5/4$.}}
@article{LenstraShmoys:90:Approximation-algorithms,
Author = {Lenstra, Jan Karel and Shmoys, David B and Tardos, {\'E}va},
Date-Added = {2016-02-22 07:50:42 +0000},
Date-Modified = {2016-02-22 07:50:47 +0000},
Journal = {Mathematical programming},
Number = {1-3},
Pages = {259--271},
Publisher = {Springer},
Title = {Approximation algorithms for scheduling unrelated parallel machines},
Volume = {46},
Year = {1990},
Annote = {$R||C_{\max}$ polynomial time approximation ratio $\geq 3/2$}}
@article{HoogeveenSchuurman:01:Non-approximability-results,
Author = {Hoogeveen, Han and Schuurman, Petra and Woeginger, Gerhard J},
Date-Added = {2016-02-22 07:36:04 +0000},
Date-Modified = {2016-02-22 10:10:09 +0000},
Journal = {INFORMS Journal on Computing},
Number = {2},
Pages = {157--168},
Publisher = {INFORMS},
Title = {Non-approximability results for scheduling problems with minsum criteria},
Volume = {13},
Year = {2001},
Annote = {$R|r_j|\sum C_j$ is APX-hard\\
$R||\sum w_jC_j$ is APX-hard\\
$F||\sum C_j$ is APX-hard\\
$O||\sum C_j$ is APX-hard\\
$P|prec;p_j=1|\sum C_j$ is APX-hard\\
$P|prec;l=1;p_j=1|\sum C_j$ is APX-hard.}}
@incollection{Skutella:06:List-scheduling,
Author = {Skutella, Martin},
Booktitle = {Efficient Approximation and Online Algorithms},
Date-Added = {2014-04-28 14:08:16 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Pages = {250--291},
Publisher = {Springer},
Title = {List scheduling in order of $\alpha$-points on a single machine},
Year = {2006},
Annote = {$1|r_j|\sum C_j$ randomized approximation ratio using $\alpha$-points $\leq 1.5820$\\
$1|r_j|\sum w_jC_j$ randomized approximation ratio using $\alpha$-points $\leq 1.6853$\\
$1|r_j;pmtn|\sum C_j$ randomized approximation ratio using $\alpha$-points $\leq 4/3$\\
$1|r_j;prec;pmtn|\sum w_jC_j$ randomized approximation ratio using $\alpha$-points $\leq 2+\epsilon$\\
$1|r_j;prec|\sum w_jC_j$ randomized approximation ratio using $\alpha$-points $\leq e+\epsilon$\\
},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QOy4uLy4uLy4uL1h0b2ZNYXRoaWV1L2JpYmxpby9Ta3V0ZWxsYS0wNi1MaXN0LXNjaGVkdWxpbmcucGRm0hcLGBlXTlMuZGF0YU8RAeQAAAAAAeQAAgAAC0Rpc3F1ZSBEdXJyAAAAAAAAAAAAAAAAAAAAANCauGlIKwAAABqRXx9Ta3V0ZWxsYS0wNi1MaXN0LXNjaGVkdWxpbmcucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGzmIz4QttAAAAAAAAAAAAAMAAwAACSAAAAAAAAAAAAAAAAAAAAAGYmlibGlvABAACAAA0JqqWQAAABEACAAAz4QRlAAAAAEAFAAakV8AGo7eABqOTQAGI6IAApOYAAIAVkRpc3F1ZSBEdXJyOlVzZXJzOgBkdXJyOgBEcm9wYm94OgBYdG9mTWF0aGlldToAYmlibGlvOgBTa3V0ZWxsYS0wNi1MaXN0LXNjaGVkdWxpbmcucGRmAA4AQAAfAFMAawB1AHQAZQBsAGwAYQAtADAANgAtAEwAaQBzAHQALQBzAGMAaABlAGQAdQBsAGkAbgBnAC4AcABkAGYADwAYAAsARABpAHMAcQB1AGUAIABEAHUAcgByABIARVVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vU2t1dGVsbGEtMDYtTGlzdC1zY2hlZHVsaW5nLnBkZgAAEwABLwAAFQACAAv//wAAgAbSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBVAGAAZwBqAGwAbgBxAHMAdQB3AIQAjgDMANEA2QLBAsMCyALTAtwC6gLuAvUC/gMDAxADEwMlAygDLQAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAMv}}
@article{SavelsberghUma:05:An-experimental-study,
Author = {Savelsbergh, Martin WP and Uma, RN and Wein, Joel},
Date-Added = {2014-04-28 14:04:48 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {INFORMS Journal on Computing},
Number = {1},
Pages = {123--136},
Publisher = {INFORMS},
Title = {An experimental study of LP-based approximation algorithms for scheduling problems},
Volume = {17},
Year = {2005},
Annote = {$1|r_j|\sum w_jC_j$ LP-based approximation algorithms are experimentally compared with combinatorial approximation algorithms
}}
@article{SchulzSkutella:02:The-power-of-alpha-points,
Author = {Schulz, Andreas S and Skutella, Martin},
Date-Added = {2014-04-28 13:14:41 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Journal of Scheduling},
Number = {2},
Pages = {121--133},
Publisher = {Wiley Online Library},
Title = {The power of $\alpha$-points in preemptive single machine scheduling},
Volume = {5},
Year = {2002},
Annote = {$1|r_j;pmtn|\sum w_jC_j$ deterministic approximation ratio $\leq 4/3$ based on $\alpha$-points\\
$1|r_j;pmtn|\sum w_jC_j$ Dyer and Wolsey's time indexed linear programming relaxation has integrality gap $\geq 8/7$\\
},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QSy4uLy4uLy4uL1h0b2ZNYXRoaWV1L2JpYmxpby9TY2h1bHpTa3V0ZWxsYS0wMi1UaGUtcG93ZXItb2YtYWxwaGEtcG9pbnRzLnBkZtIXCxgZV05TLmRhdGFPEQIUAAAAAAIUAAIAAAtEaXNxdWUgRHVycgAAAAAAAAAAAAAAAAAAAADQmrhpSCsAAAAakV8fU2NodWx6U2t1dGVsbGEtMDItVGgjMUIzRDRFLnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABs9Ts+EKOYAAAAAAAAAAAADAAMAAAkgAAAAAAAAAAAAAAAAAAAABmJpYmxpbwAQAAgAANCaqlkAAAARAAgAAM+EDMYAAAABABQAGpFfABqO3gAajk0ABiOiAAKTmAACAFZEaXNxdWUgRHVycjpVc2VyczoAZHVycjoARHJvcGJveDoAWHRvZk1hdGhpZXU6AGJpYmxpbzoAU2NodWx6U2t1dGVsbGEtMDItVGgjMUIzRDRFLnBkZgAOAGAALwBTAGMAaAB1AGwAegBTAGsAdQB0AGUAbABsAGEALQAwADIALQBUAGgAZQAtAHAAbwB3AGUAcgAtAG8AZgAtAGEAbABwAGgAYQAtAHAAbwBpAG4AdABzAC4AcABkAGYADwAYAAsARABpAHMAcQB1AGUAIABEAHUAcgByABIAVVVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vU2NodWx6U2t1dGVsbGEtMDItVGhlLXBvd2VyLW9mLWFscGhhLXBvaW50cy5wZGYAABMAAS8AABUAAgAL//8AAIAG0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVQBgAGcAagBsAG4AcQBzAHUAdwCEAI4A3ADhAOkDAQMDAwgDEwMcAyoDLgM1Az4DQwNQA1MDZQNoA20AAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADbw==}}
@article{ChekuriMotwani:99:Precedence-constrained,
Author = {Chekuri, Chandra and Motwani, Rajeev},
Date-Added = {2014-04-28 13:10:48 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Discrete Applied Mathematics},
Number = {1},
Pages = {29--38},
Publisher = {Elsevier},
Title = {Precedence constrained scheduling to minimize sum of weighted completion times on a single machine},
Volume = {98},
Year = {1999},
Annote = {$1|prec|\sum w_jC_j$ deterministic approximation ratio $\leq 2$
},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QSC4uLy4uLy4uL1h0b2ZNYXRoaWV1L2JpYmxpby9DaGVrdXJpTW90d2FuaS05OS1QcmVjZWRlbmNlLWNvbnN0cmFpbmVkLnBkZtIXCxgZV05TLmRhdGFPEQIKAAAAAAIKAAIAAAtEaXNxdWUgRHVycgAAAAAAAAAAAAAAAAAAAADQmrhpSCsAAAAakV8fQ2hla3VyaU1vdHdhbmktOTktUHIjMUIzRDQ4LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABs9SM+EICMAAAAAAAAAAAADAAMAAAkgAAAAAAAAAAAAAAAAAAAABmJpYmxpbwAQAAgAANCaqlkAAAARAAgAAM+EBAMAAAABABQAGpFfABqO3gAajk0ABiOiAAKTmAACAFZEaXNxdWUgRHVycjpVc2VyczoAZHVycjoARHJvcGJveDoAWHRvZk1hdGhpZXU6AGJpYmxpbzoAQ2hla3VyaU1vdHdhbmktOTktUHIjMUIzRDQ4LnBkZgAOAFoALABDAGgAZQBrAHUAcgBpAE0AbwB0AHcAYQBuAGkALQA5ADkALQBQAHIAZQBjAGUAZABlAG4AYwBlAC0AYwBvAG4AcwB0AHIAYQBpAG4AZQBkAC4AcABkAGYADwAYAAsARABpAHMAcQB1AGUAIABEAHUAcgByABIAUlVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vQ2hla3VyaU1vdHdhbmktOTktUHJlY2VkZW5jZS1jb25zdHJhaW5lZC5wZGYAEwABLwAAFQACAAv//wAAgAbSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBVAGAAZwBqAGwAbgBxAHMAdQB3AIQAjgDZAN4A5gL0AvYC+wMGAw8DHQMhAygDMQM2A0MDRgNYA1sDYAAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANi}}
@inproceedings{AfratiBampis:99:Approximation-schemes,
Author = {Afrati, Foto and Bampis, Evripidis and Chekuri, Chandra and Karger, David and Kenyon, Claire and Khanna, Sanjeev and Milis, Ioannis and Queyranne, Maurice and Skutella, Martin and Stein, Clifford and others},
Booktitle = {Foundations of Computer Science, 1999. 40th Annual Symposium on},
Date-Added = {2014-04-28 12:35:04 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Organization = {IEEE},
Pages = {32--43},
Title = {Approximation schemes for minimizing average weighted completion time with release dates},
Year = {1999},
Annote = {$P|r_j|\sum w_jC_j$ has a PTAS\\
$P|r_j;pmtn|\sum w_jC_j$ has a PTAS\\
$Rm|r_j|\sum w_jC_j$ has a PTAS\\
$Rm|r_j;pmtn|\sum w_jC_j$ has a PTAS\\
},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QRS4uLy4uLy4uL1h0b2ZNYXRoaWV1L2JpYmxpby9BZnJhdGlCYW1waXMtOTktQXBwcm94aW1hdGlvbi1zY2hlbWVzLnBkZtIXCxgZV05TLmRhdGFPEQICAAAAAAICAAIAAAtEaXNxdWUgRHVycgAAAAAAAAAAAAAAAAAAAADQmrhpSCsAAAAakV8fQWZyYXRpQmFtcGlzLTk5LUFwcHIjMUIzRDA4LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABs9CM+EF6sAAAAAAAAAAAADAAMAAAkgAAAAAAAAAAAAAAAAAAAABmJpYmxpbwAQAAgAANCaqlkAAAARAAgAAM+D+4sAAAABABQAGpFfABqO3gAajk0ABiOiAAKTmAACAFZEaXNxdWUgRHVycjpVc2VyczoAZHVycjoARHJvcGJveDoAWHRvZk1hdGhpZXU6AGJpYmxpbzoAQWZyYXRpQmFtcGlzLTk5LUFwcHIjMUIzRDA4LnBkZgAOAFQAKQBBAGYAcgBhAHQAaQBCAGEAbQBwAGkAcwAtADkAOQAtAEEAcABwAHIAbwB4AGkAbQBhAHQAaQBvAG4ALQBzAGMAaABlAG0AZQBzAC4AcABkAGYADwAYAAsARABpAHMAcQB1AGUAIABEAHUAcgByABIAT1VzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vQWZyYXRpQmFtcGlzLTk5LUFwcHJveGltYXRpb24tc2NoZW1lcy5wZGYAABMAAS8AABUAAgAL//8AAIAG0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVQBgAGcAagBsAG4AcQBzAHUAdwCEAI4A1gDbAOMC6QLrAvAC+wMEAxIDFgMdAyYDKwM4AzsDTQNQA1UAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADVw==}}
@inproceedings{SchulzSkutella:97:Scheduling-LPs-bear,
Author = {Schulz, Andreas S and Skutella, Martin},
Booktitle = {Algorithms---ESA'97},
Date-Added = {2014-04-28 12:13:58 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Organization = {Springer},
Pages = {416--429},
Title = {Scheduling-LPs bear probabilities randomized approximations for min-sum criteria},
Year = {1997},
Annote = {$R|r_j|\sum w_jC_j$ randomized approximation ratio $\leq 2+\epsilon$\\
$P|r_j|\sum w_jC_j$ randomized approximation ratio $\leq 2$\\
$1|r_j|\sum w_jC_j$ randomized approximation ratio $\leq 1.6853$ in time $O(n\log n)$\\
$1|r_j;pmtn|\sum w_jC_j$ randomized approximation ratio $\leq 4/3$
},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QRS4uLy4uLy4uL1h0b2ZNYXRoaWV1L2JpYmxpby9TY2h1bHpTa3V0ZWxsYS05Ny1TY2hlZHVsaW5nLUxQcy1iZWFyLnBkZtIXCxgZV05TLmRhdGFPEQICAAAAAAICAAIAAAtEaXNxdWUgRHVycgAAAAAAAAAAAAAAAAAAAADQmrhpSCsAAAAakV8fU2NodWx6U2t1dGVsbGEtOTctU2MjMUIzOTk3LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABs5l8+EEroAAAAAAAAAAAADAAMAAAkgAAAAAAAAAAAAAAAAAAAABmJpYmxpbwAQAAgAANCaqlkAAAARAAgAAM+D9poAAAABABQAGpFfABqO3gAajk0ABiOiAAKTmAACAFZEaXNxdWUgRHVycjpVc2VyczoAZHVycjoARHJvcGJveDoAWHRvZk1hdGhpZXU6AGJpYmxpbzoAU2NodWx6U2t1dGVsbGEtOTctU2MjMUIzOTk3LnBkZgAOAFQAKQBTAGMAaAB1AGwAegBTAGsAdQB0AGUAbABsAGEALQA5ADcALQBTAGMAaABlAGQAdQBsAGkAbgBnAC0ATABQAHMALQBiAGUAYQByAC4AcABkAGYADwAYAAsARABpAHMAcQB1AGUAIABEAHUAcgByABIAT1VzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vU2NodWx6U2t1dGVsbGEtOTctU2NoZWR1bGluZy1MUHMtYmVhci5wZGYAABMAAS8AABUAAgAL//8AAIAG0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVQBgAGcAagBsAG4AcQBzAHUAdwCEAI4A1gDbAOMC6QLrAvAC+wMEAxIDFgMdAyYDKwM4AzsDTQNQA1UAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADVw==}}
@inproceedings{Goemans:97:Improved-approximation,
Author = {Goemans, Michel X},
Booktitle = {Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms},
Date-Added = {2014-04-28 12:07:46 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Organization = {Society for Industrial and Applied Mathematics},
Pages = {591--598},
Title = {Improved approximation algorthims for scheduling with release dates},
Year = {1997},
Annote = {$1|r_j|\sum w_jC_j$ deterministic approximation ratio $\leq 2$ in time $O(n^2)$
},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QQS4uLy4uLy4uL1h0b2ZNYXRoaWV1L2JpYmxpby9Hb2VtYW5zLTk3LUltcHJvdmVkLWFwcHJveGltYXRpb24ucGRm0hcLGBlXTlMuZGF0YU8RAfYAAAAAAfYAAgAAC0Rpc3F1ZSBEdXJyAAAAAAAAAAAAAAAAAAAAANCauGlIKwAAABqRXx9Hb2VtYW5zLTk3LUltcHJvdmVkLSMxQjM5OTQucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGzmUz4QRkQAAAAAAAAAAAAMAAwAACSAAAAAAAAAAAAAAAAAAAAAGYmlibGlvABAACAAA0JqqWQAAABEACAAAz4P1cQAAAAEAFAAakV8AGo7eABqOTQAGI6IAApOYAAIAVkRpc3F1ZSBEdXJyOlVzZXJzOgBkdXJyOgBEcm9wYm94OgBYdG9mTWF0aGlldToAYmlibGlvOgBHb2VtYW5zLTk3LUltcHJvdmVkLSMxQjM5OTQucGRmAA4ATAAlAEcAbwBlAG0AYQBuAHMALQA5ADcALQBJAG0AcAByAG8AdgBlAGQALQBhAHAAcAByAG8AeABpAG0AYQB0AGkAbwBuAC4AcABkAGYADwAYAAsARABpAHMAcQB1AGUAIABEAHUAcgByABIAS1VzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vR29lbWFucy05Ny1JbXByb3ZlZC1hcHByb3hpbWF0aW9uLnBkZgAAEwABLwAAFQACAAv//wAAgAbSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBVAGAAZwBqAGwAbgBxAHMAdQB3AIQAjgDSANcA3wLZAtsC4ALrAvQDAgMGAw0DFgMbAygDKwM9A0ADRQAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANH}}
@inproceedings{HoogeveenVestjens:96:Optimal-On-Line,
Author = {Han Hoogeveen and Arjen P. A. Vestjens},
Bibsource = {DBLP, http://dblp.uni-trier.de},
Booktitle = {IPCO},
Editor = {William H. Cunningham and S. Thomas McCormick and Maurice Queyranne},
Isbn = {3-540-61310-2},
Publisher = {Springer},
Series = {Lecture Notes in Computer Science},
Title = {Integer Programming and Combinatorial Optimization, 5th International IPCO Conference, Vancouver, British Columbia, Canada, June 3-5, 1996, Proceedings},
Volume = {1084},
Date-Added = {2014-04-28 11:58:59 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Ee = {http://dx.doi.org/10.1007/3-540-61310-2_30},
Pages = {404-414},
Title = {Optimal On-Line Algorithms for Single-Machine Scheduling},
Year = {1996},
Annote = {$1|r_j|\sum w_jC_j$ deterministic approximation ratio $\leq 2$\\
$1|online-r_j|\sum w_jC_j$ deterministic approximation ratio $\leq 2$\\
$1|online-r_j|\sum w_jC_j$ deterministic approximation ratio $\geq 2$\\
},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QRC4uLy4uLy4uL1h0b2ZNYXRoaWV1L2JpYmxpby9Ib29nZXZlZW5WZXN0amVucy05Ni1PcHRpbWFsLU9uLUxpbmUucGRm0hcLGBlXTlMuZGF0YU8RAf4AAAAAAf4AAgAAC0Rpc3F1ZSBEdXJyAAAAAAAAAAAAAAAAAAAAANCauGlIKwAAABqRXx9Ib29nZXZlZW5WZXN0amVucy05NiMxQjNEMDEucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGz0Bz4QWOAAAAAAAAAAAAAMAAwAACSAAAAAAAAAAAAAAAAAAAAAGYmlibGlvABAACAAA0JqqWQAAABEACAAAz4P6GAAAAAEAFAAakV8AGo7eABqOTQAGI6IAApOYAAIAVkRpc3F1ZSBEdXJyOlVzZXJzOgBkdXJyOgBEcm9wYm94OgBYdG9mTWF0aGlldToAYmlibGlvOgBIb29nZXZlZW5WZXN0amVucy05NiMxQjNEMDEucGRmAA4AUgAoAEgAbwBvAGcAZQB2AGUAZQBuAFYAZQBzAHQAagBlAG4AcwAtADkANgAtAE8AcAB0AGkAbQBhAGwALQBPAG4ALQBMAGkAbgBlAC4AcABkAGYADwAYAAsARABpAHMAcQB1AGUAIABEAHUAcgByABIATlVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vSG9vZ2V2ZWVuVmVzdGplbnMtOTYtT3B0aW1hbC1Pbi1MaW5lLnBkZgATAAEvAAAVAAIAC///AACABtIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFUAYABnAGoAbABuAHEAcwB1AHcAhACOANUA2gDiAuQC5gLrAvYC/wMNAxEDGAMhAyYDMwM2A0gDSwNQAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAA1I=}}
@article{ChekuriMotwani:01:Approximation-techniques,
Author = {Chekuri, Chandra and Motwani, Rajeev and Natarajan, Balas and Stein, Clifford},
Date-Added = {2014-04-28 11:34:04 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {SIAM Journal on Computing},
Number = {1},
Pages = {146--166},
Publisher = {SIAM},
Title = {Approximation techniques for average completion time scheduling},
Volume = {31},
Year = {2001},
Annote = {$1|r_j|\sum w_jC_j$ randomized approximation ratio $\leq e/(e-1) \approx 1.58$ by algorithm BEST-$\alpha$\\
$1|r_j|\sum w_jC_j$ randomized (oblivious model) competitive ratio $\leq e/(e-1) \approx 1.58$ by algorithm BEST-$\alpha$\\
},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QSi4uLy4uLy4uL1h0b2ZNYXRoaWV1L2JpYmxpby9DaGVrdXJpTW90d2FuaS0wMS1BcHByb3hpbWF0aW9uLXRlY2huaXF1ZXMucGRm0hcLGBlXTlMuZGF0YU8RAhAAAAAAAhAAAgAAC0Rpc3F1ZSBEdXJyAAAAAAAAAAAAAAAAAAAAANCauGlIKwAAABqRXx9DaGVrdXJpTW90d2FuaS0wMS1BcCMxQjM5OTkucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGzmZz4QLOgAAAAAAAAAAAAMAAwAACSAAAAAAAAAAAAAAAAAAAAAGYmlibGlvABAACAAA0JqqWQAAABEACAAAz4PvGgAAAAEAFAAakV8AGo7eABqOTQAGI6IAApOYAAIAVkRpc3F1ZSBEdXJyOlVzZXJzOgBkdXJyOgBEcm9wYm94OgBYdG9mTWF0aGlldToAYmlibGlvOgBDaGVrdXJpTW90d2FuaS0wMS1BcCMxQjM5OTkucGRmAA4AXgAuAEMAaABlAGsAdQByAGkATQBvAHQAdwBhAG4AaQAtADAAMQAtAEEAcABwAHIAbwB4AGkAbQBhAHQAaQBvAG4ALQB0AGUAYwBoAG4AaQBxAHUAZQBzAC4AcABkAGYADwAYAAsARABpAHMAcQB1AGUAIABEAHUAcgByABIAVFVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vQ2hla3VyaU1vdHdhbmktMDEtQXBwcm94aW1hdGlvbi10ZWNobmlxdWVzLnBkZgATAAEvAAAVAAIAC///AACABtIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFUAYABnAGoAbABuAHEAcwB1AHcAhACOANsA4ADoAvwC/gMDAw4DFwMlAykDMAM5Az4DSwNOA2ADYwNoAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAA2o=}}
@article{KellererStrusevich:06:A-fully-polynomial,
Author = {Kellerer, H. and Strusevich, V.A.},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Theoretical computer science},
Number = {1},
Pages = {230--238},
Publisher = {Elsevier},
Title = {A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date},
Volume = {369},
Year = {2006},
Annote = {$1 | d_j=d | \sum w_jT_j$ has an FPTAS}}
@article{Jinjiang:92:The-NP-hardness-of-the-single,
Author = {JUAN Jinjiang},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {System Science and Mathematical Sciences},
Number = {4},
Pages = {328--333},
Title = {The {NP}-hardness of the single machine common due date weighted tardiness problem},
Volume = {5},
Year = {1992},
Annote = {$1 | d_j=d | \sum w_jT_j$ is $\NP$-hard}}
@article{LawlerMoore:69:A-functional-equation,
Author = {Lawler, E.L. and Moore, J.M.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Management Sci.},
Pages = {77-84},
Number = {1},
Publisher = {INFORMS},
Title = {A functional equation and its application to resource allocation and sequencing problems},
Volume = 16,
Year = 1969,
Annote = {$1||\sum w_jU_j$ is in $P_{pseudo}$,\\
$1 | d_j=d | \sum w_jT_j$ is in $P_{pseudo}$ with time complexity $O(n^2d)$\\
$1||\sum w_jU_j$ is NP-hard.}}
@inproceedings{ManaaHanen:10:On-scheduling-with,
Author = {Manaa, A. and Hanen, C.},
Booktitle = {Proceedings of the {E}uropean {C}onference of {O}perational, {R}esearch (EURO, {L}isbon)},
Date-Modified = {2015-12-21 23:13:08 +0000},
Title = {On scheduling with negative time lags},
Year = {2010},
Annote = {$1|p_j=1;prec;l_{ij}\leq0|L_{\max}$ is $\NP$-hard by reduction from 3-SAT.}}
@article{BaptisteBrucker:15:The-Complexity-of-Mean,
Author = {Philippe Baptiste and Peter Brucker and Marek Chrobak and Christoph D{\"u}rr and Svetlana A. Kravchenko and Francis Sourd},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Journal of Scheduling},
Title = {The Complexity of Mean Flow Time Scheduling Problems with Release Times},
Year = {to appear},
Annote = {$P | r_j;pmtn;p_j=p | \sum C_j$ is solvable by a linear program of size $O(nm)$}}
@article{Bellenguez.ea:15:A-Note-on-NP-Hardness,
author = {Odile Bellenguez-Morineau and Marek Chrobak and Christoph D\"urr and Damien Prot},
title = {A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines},
journaltitle = {Journal of Scheduling},
volume = {18},
number = {3},
pages = {299--304},
year = {2015},
Annote = {$P | r_j;pmtn| \sum C_j$ is strongly NP-hard}
}
@inproceedings{DurrHurand:06:Finding-total,
Author = {Christoph D{\"u}rr and Mathilde Hurand},
Booktitle = {Proc. of the 14th Annual European Symposium on Algorithms (ESA)},
Date-Modified = {2015-12-21 23:13:08 +0000},
Title = {Finding total unimodularity in optimization problems solved by linear programs},
Year = {2006},
Annote = {$P|r_j;p_j=1;size_j\in\{1,m\}|L_{\max}$ the decision version is solvable in $O(n^3)$.}}
@article{ChrobakDurr:06:A-Note-on-Scheduling,
Author = {Marek Chrobak and Christoph D{{\"u}}rr and Wojciech Jawor and Lukasz Kowalik and Maciej Kurowski},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Journal of Scheduling},
Number = {1},
Pages = {71--73},
Title = {A Note on Scheduling Equal-Length Jobs to Maximize Throughput},
Volume = {9},
Year = {2006},
Annote = {$1|r_j;p_j=p|\sum U_j$ is solvable in $O(n^5)$.}}
@article{BaptisteChrobak:04:Preemptive-scheduling,
Author = {Baptiste, Philippe and Chrobak, Marek and D{\"u}rr, Christoph and Jawor, Wojciech and Vakhania, Nodari},
Date-Modified = {2015-12-21 23:13:08 +0000},
Fjournal = {Operations Research Letters},
Number = {3},
Pages = {258--264},
Title = {Preemptive scheduling of equal-length jobs to maximize weighted throughput},
Volume = {32},
Year = {2004},
Annote = {$1|r_j;pmtn;p_j=p|\sum w_jU_j$ is solvable in $O(n^4)$.}}
@article{BaptisteSchieber:03:A-note-on-scheduling,
Author = {Baptiste, P. and Schieber, B.},
Date-Modified = {2015-12-21 23:13:08 +0000},
Fjournal = {Journal of Scheduling},
Journal = {J. Sched.},
Number = 4,
Pages = {395-404},
Title = {A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness},
Volume = 6,
Year = 2003,
Annote = {$P2|r_j;p_j=1;size_j|L_{\max}$ is in $P$\\
$P|r_j;p_j=1;size_j\in\{1,m\}|L_{\max}$ can be decided with an LP of $O(n^2)$ var.}}
@unpublished{ProtBellenguez-Morineau:12:,
Author = {D. Prot and O. Bellenguez-Morineau and C. Lahlou},
Date-Modified = {2015-12-21 23:13:08 +0000},
Note = {personal communcation},
Year = {2012},
Annote = {$P|r_j;pmtn|\sum C_j$ NP-hardness proof of [BBCDKS] has a bug}}