%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Christoph Durr at 2015-12-11 17:58:16 +0100
%% Saved with string encoding Occidental (Windows Latin 1)
@article{BadicsBoros:98:HP-minimization,
Author = {Badics, T. and Boros, E.},
Journal = {Mathematics of Operations Research},
Number = {3},
Pages = {649-600},
Title = {Minimization of half-products},
Volume = {23},
Year = {1998}}
@article{ErelGhosh:08:FPTAS-HP-minimization,
Author = {Erdal Erel and Jay B. Ghosh},
Journal = {Discrete Applied Mathematics},
Number = {15},
Pages = {3046-3056},
Title = {{FPTAS} for half-products minimization with scheduling applications},
Volume = {156},
Year = {2008}}
@article{IbarraKim:75:Subsetsum-Algorithm,
Address = {New York, NY, USA},
Author = {Ibarra, Oscar H. and Kim, Chul E.},
Journal = {Journal of the ACM (JACM)},
Number = {4},
Pages = {463--468},
Publisher = {ACM},
Title = {Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems},
Volume = {22},
Year = {1975}}
@article{JurischKubiakJozefowska:97:Minclique-algorithm,
Author = {Bernd Jurisch and Wieslaw Kubiak and Joanna Jozefowska},
Journal = {Discrete Applied Mathematics},
Number = 1,
Pages = {115--139},
Title = {Algorithms for minclique scheduling problems},
Volume = 72,
Year = 1997}
@article{GrahamLawlerLenstraKan:79:Problem-Notation,
Author = {Graham, R.L. and Lawler, E.L. and Lenstra, J.K. and Kan, A.H.G.R.},
Journal = {Annals of Discrete Mathematics},
Number = {2},
Pages = {287--326},
Title = {Optimization and approximation in deterministic sequencing and scheduling: A survey},
Volume = {5},
Year = {1979}}
@book{GamowStern:58:Puzzle-Math,
Author = {Gamow, George and Stern, Marvin},
Publisher = {Macmillan},
Title = {Puzzle-math},
Year = {1958}}
@book{GareyJohnson:79:Complexity,
Author = {M. R. Garey and David S. Johnson},
Publisher = {W. H. Freeman},
Title = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
Year = {1979}}
@book{Nisan:07:Algorithmic-game-theory,
Author = {Nisan, Noam},
Publisher = {Cambridge University Press},
Title = {Algorithmic game theory},
Year = {2007}}
@book{EasleyKleinberg:10:Networks,
Author = {Easley, David and Kleinberg, Jon},
Publisher = {Cambridge University Press},
Title = {Networks, crowds, and markets},
Year = {2010}}
@article{Woeginger:10:OpenProblems,
Address = {Dagstuhl, Germany},
Author = {Gerhard J. Woeginger},
Editor = {Susanne Albers and Sanjoy K. Baruah and Rolf H. M{\"o}hring and Kirk Pruhs},
Issn = {1862-4405},
Journal = {Dagstuhl Research Online Publication Server},
Pages = {24},
Publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
Title = {{Scheduling (Dagstuhl Seminar 10071)}},
Url = {http://drops.dagstuhl.de/opus/volltexte/2010/2536},
Year = {2010},
Bdsk-Url-1 = {http://drops.dagstuhl.de/opus/volltexte/2010/2536}}
@article{Hohn:13:OpenProblems,
Address = {Dagstuhl, Germany},
Author = {W. H{\"o}hn},
Editor = {Susanne Albers and Onno J. Boxma and Kirk Pruhs},
Issn = {2192-5283},
Journal = {Dagstuhl Research Online Publication Server},
Pages = {32--33},
Publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
Title = {{Scheduling (Dagstuhl Seminar 13111)}},
Url = {http://drops.dagstuhl.de/opus/volltexte/2013/4024},
Year = {2013},
Bdsk-Url-1 = {http://drops.dagstuhl.de/opus/volltexte/2013/4024}}
@article{HartNilssonBertram:72:Proposition-A-star-algorithm,
Author = {Hart, Peter E and Nilsson, Nils J and Raphael, Bertram},
Journal = {ACM SIGART Bulletin},
Pages = {28--29},
Publisher = {ACM},
Title = {Correction to a formal basis for the heuristic determination of minimum cost paths},
Volume = {37},
Year = {1972}}
@article{SenBagchiRamaswamy:96:A-star-algorithm-for-scheduling-problems,
Author = {Sen, Anup K and Bagchi, Amitava and Ramaswamy, Ramkumar},
Journal = {IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans},
Number = {1},
Pages = {168--173},
Publisher = {IEEE},
Title = {Searching graphs with {A*}: applications to job sequencing},
Volume = {26},
Year = {1996}}
@article{KaindlKainzRadda:01:Asymmetry-in-search-for-A-star-algorithm,
Author = {Kaindl, H. and Kainz, G. and Radda, K.},
Journal = {IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics},
Number = {5},
Pages = {791--796},
Publisher = {IEEE},
Title = {Asymmetry in search},
Volume = {31},
Year = {2001}}
@misc{Hohn:12:Library-quadratic-penalty-function,
Author = {Wibke H\"ohn and Tobias Jacobs},
Howpublished = {``http://www.coga.tu-berlin.de/v-menue/projekte/complex\_scheduling/generalized\_min-sum\_scheduling\_jnstance\_library/''},
Title = {Generalized min sum scheduling instance library},
Year = 2012}
@inproceedings{HohnJacobs:12:Experimental-analytical-quadratic-penalty-function,
Author = {H{\"o}hn, Wiebke. and Jacobs, Tobias.},
Booktitle = {Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX'12)},
Pages = {103-117},
Title = {An experimental and analytical study of order constraints for single machine scheduling with quadratic cost},
Year = {2012}}
@article{MondalSen:00:Conjecture-order-constraint-quadratic-penalty-function,
Author = {Mondal, S.A. and Sen, A.K.},
Journal = {European Journal of Operational Research},
Number = {2},
Pages = {425--428},
Publisher = {Elsevier},
Title = {An improved precedence rule for single machine sequencing problems with quadratic penalty},
Volume = {125},
Year = {2000}}
@article{SenDileepan:90:Order-constraint-generalized-quadratic-penalty-function,
Author = {Sen, T. and Dileepan, P. and Ruparel, B.},
Journal = {Engineering Costs and Production Economics},
Number = {3},
Pages = {197--202},
Publisher = {Elsevier},
Title = {Minimizing a generalized quadratic penalty function of job completion times: an improved branch-and-bound approach},
Volume = {18},
Year = {1990}}
@inproceedings{CroceTadeiBarracoDiTullio:93:Order-constraint-generalized-quadratic-penalty-function,
Author = {Croce, F.D. and Tadei, R. and Baracco, P. and Di Tullio, R.},
Booktitle = {Proc. of the IEEE International Conference on Robotics and Automation},
Pages = {816--820},
Title = {On minimizing the weighted sum of quadratic completion times on a single machine},
Year = {1993}}
@article{BaggaKarlra:80:Order-constraint-quadratic-penalty-function,
Author = {Bagga, P.C. and Karlra, K.R.},
Journal = {Management Science},
Number = {6},
Pages = {633--636},
Publisher = {JSTOR},
Title = {A node elimination procedure for {T}ownsend's algorithm for solving the single machine quadratic penalty function scheduling problem},
Volume = {26},
Year = {1980}}
@article{Townsend:78:Order-constraint-quadratic-penalty-function,
Author = {Townsend, W.},
Journal = {Management Science},
Number = {5},
Pages = {530--534},
Publisher = {JSTOR},
Title = {The single machine problem with quadratic penalty function of completion times: a branch-and-bound solution},
Volume = {24},
Year = {1978}}
@article{Szwarc:98:Decomposition-for-non-linear-penalty-function,
Author = {Szwarc, W.},
Journal = {Annals of Operations Research},
Pages = {271--287},
Publisher = {Springer},
Title = {Decomposition in single-machine scheduling},
Volume = {83},
Year = {1998}}
@article{Alidaee:93:Order-constraint-for-non-linear-penalty-function,
Author = {Alidaee, B.},
Journal = {Journal of the Operational Research Society},
Number = {2},
Pages = {125--132},
Publisher = {JSTOR},
Title = {Numerical methods for single machine scheduling with non-linear cost functions to minimize total cost},
Volume = {44},
Year = {1993}}
@inproceedings{HohnJacobs:12:Performance-Smith-rule,
Author = {H\"ohn, Wiebke and Jacobs, Tobias},
Booktitle = {Proc. of the 10th Latin American Theoretical Informatics Symposium (LATIN)},
Pages = {482-493},
Title = {On the performance of {S}mith's rule in single-machine scheduling with nonlinear cost},
Year = {2012},
Annote = {$1 ||\sum{w_jf(C_j)}$, $f$ piecewise linear is unary $NP$-hard}}
@inproceedings{MegowVerschae:13:PTAS-piecewise-penalty-function,
Author = {Nicole Megow and Jos{\'e} Verschae},
Booktitle = {Proc. of the 40th International Colloquium on Automata, Languages and Programming (ICALP)},
Pages = {745-756},
Title = {Dual Techniques for Scheduling on a Machine with Varying Speed},
Year = {2013},
Annote = {$1 ||\sum{w_jf(C_j)}$, $f$ piecewise linear can be solved in $2^{O(\log(1/\varepsilon)/\varepsilon^2)}\log(\sum_j w_j)n$.}}
@article{Smith:56:Linear-penalty-function,
Author = {Smith, Wayne E.},
Journal = {Naval Research Logistics Quarterly},
Number = {1-2},
Pages = {59--66},
Publisher = {Wiley Online Library},
Title = {Various optimizers for single-stage production},
Volume = {3},
Year = {1956},
Annote = {$1 ||\sum w_jC_j$ can be solved in time $O(n \log n)$}}
@article{Rothkopf:66:Exponential-penalty-function,
Author = {Rothkopf, Michael H},
Journal = {Management Science},
Number = {5},
Pages = {437--447},
Publisher = {INFORMS},
Title = {Scheduling independent tasks on parallel processors},
Volume = {12},
Year = {1966},
Annote = {$1 ||\sum{w_je^{C_j}}$ can be solved in time $O(n\log n)$}}
@article{ChengLiu:04:Parallel-quadratic-penalty-function,
Author = {Cheng, TC Edwin and Liu, Zhaohui},
Journal = {IIE transactions},
Number = {1},
Pages = {11--17},
Publisher = {Taylor \& Francis},
Title = {Parallel machine scheduling to minimize the sum of quadratic completion times},
Volume = {36},
Year = {2004},
Annote = {$P ||\sum{w_jC_j^2}$ is unary $NP$-hard}}
@article{Yuan:92:Weighted-tardiness-common-due-date-penalty-function,
Author = {Yuan, J.},
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 ||\sum{w_j\max\{0,C_j-d\}}$ is binary $NP$-hard}}
@article{LawlerMoore:69:Pseudo-weighted-tardiness-common-due-date-penalty-function,
Author = {Lawler, E. L. and Moore, J. M.},
Journal = {Management Science},
Number = {1},
Pages = {77-84},
Title = {A Functional Equation and its Application to Resource Allocation and Sequencing Problems},
Volume = {16},
Year = {1969},
Annote = {$1 |w_j=1|\sum{w_j\max\{0,C_j-d\}}$ can be solved in time $O(n^2)$}}
@article{KellererStrusevich:06:FPTAS-weighted-tardiness-common-due-date-penalty-function,
Author = {Hans Kellerer and Vitaly A. Strusevich},
Journal = {Theoretical Computer Science},
Number = 1,
Pages = {230--238},
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 ||\sum{w_j\max\{0,C_j-d\}}$ can be solved in time $O((n^6 \log \sum_j w_j)/ \varepsilon^3)$}}
@article{Kacem:10:FPTAS-weighted-tardiness-common-due-date-penalty-function,
Author = {Imed Kacem},
Journal = {Discrete Applied Mathematics},
Number = {9},
Pages = {1035--1040},
Title = {Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date},
Volume = {158},
Year = 2010,
Annote = {$1 ||\sum{w_j\max\{0,C_j-d\}}$ can be solved in time $O(n^2/\varepsilon)$}}
@unpublished{Verschae:13:FPTAS-weighted-tardiness-common-due-date-completion-time-penalty-function,
Author = {Jos{\'e} Verschae},
Month = {August},
Title = {Personal communication},
Year = {2013},
Annote = {$1 ||\sum{w_jC_j+\max\{0,C_j-d\}}$ can be solved in time $O(n^3\log d/\varepsilon^2)$}}
@article{ChengNgYuanLiu:05:Weighted-earliness-common-due-date-penalty-function,
Author = {Cheng, T.C.E. and Ng, C.T. and Yuan, J.J. and Liu, Z.H.},
Journal = {European Journal of Operational Research},
Number = {2},
Pages = {423--443},
Publisher = {Elsevier},
Title = {Single machine scheduling to minimize total weighted tardiness},
Volume = {165},
Year = {2005},
Annote = {$1 ||\sum{w_j\max\{d-C_j,0\}}$ can be solved in time$O(n^4/\varepsilon)$}}
@article{DuLeung:00:Weighted-tardiness-due-date-penalty-function,
Author = {Du, J. and Leung, J.Y.T.},
Journal = {Mathematics of Operations Research},
Number = {3},
Pages = {483--495},
Publisher = {JSTOR},
Title = {Minimizing total tardiness on one machine is {NP}-hard},
Volume = {15},
Year = {1990},
Annote = {$1 ||\sum{w_j\max\{C_j-d_j,0\}}$ is binary $NP$-hard}}
@article{HallKubiakSethi:91:Absolute-deviation-small-common-due-date-penalty-function,
Author = {Hall, N.G. and Kubiak, W. and Sethi, S.P.},
Journal = {Operations Research},
Number = {5},
Pages = {847--856},
Publisher = {JSTOR},
Title = {Earliness-tardiness scheduling problems, {II}: Deviation of completion times about a restrictive common due date},
Volume = {39},
Year = {1991},
Annote = {$1 |w_j=1|\sum{w_j|C_j-d|}$, $d<\sum{p_j}$ can be solved in time $O(n\sum_j p_j)$}}
@article{HoogeveenVanDeVelde:91:Absolute-deviation-small-common-due-date-penalty-function,
Author = {Hoogeveen, J.A. and Van de Velde, S.L.},
Journal = {European Journal of Operational Research},
Number = {2},
Pages = {237--242},
Publisher = {Elsevier},
Title = {Scheduling around a small common due date},
Volume = {55},
Year = {1991},
Annote = {$1 |w_j=w|\sum{w_j|C_j-d|}$, $d<\sum{p_j}$ can be solved in time $O(n^2d)$}}
@article{KellererVitaly:10:FPTAS-absolute-deviation-small-common-due-date-penalty-function,
Author = {Kellerer, Hans and Vitaly, A Strusevich},
Journal = {International Journal of Foundations of Computer Science},
Number = {3},
Pages = {357--383},
Publisher = {World Scientific},
Title = {Minimizing total weighted earliness-tardiness on a single machine around a small common due date: An {FPTAS} using quadratic knapsack},
Volume = {21},
Year = {2010},
Annote = {$1 ||\sum{w_j\max\{d-C_j,0\}}$, $d<\sum{p_j}$ can be solved in time $O(n^6/\varepsilon^3)$}}
@article{HallPosner:91:Absolute-deviation-large-common-due-date-penalty-function,
Author = {Hall, N.G. and Posner, M.E.},
Journal = {Operations Research},
Number = {5},
Pages = {836--846},
Publisher = {JSTOR},
Title = {Earliness-tardiness scheduling problems,{I}: Weighted deviation of completion times about a common due date},
Volume = {39},
Year = {1991},
Annote = {$1 |w_j=w|\sum{w_j|C_j-d|}$, $d\geq\sum{p_j}$ is in P}}
@article{Kanet:81:Unweighted-absolute-deviation-large-common-due-date-penalty-function,
Author = {Kanet, John J.},
Journal = {Naval Research Logistics Quarterly},
Number = {4},
Pages = {643--651},
Publisher = {Wiley Subscription Services, Inc., A Wiley Company},
Title = {Minimizing the average deviation of job completion times about a common due date},
Volume = {28},
Year = {1981},
Annote = {$1 |w_j=1|\sum{w_j|C_j-d|}$, $d\geq\sum{p_j}$ is in P}}
@article{BagchiUttarayanSullivan:86:Unweighted-absolute-deviation-large-common-due-date-penalty-function,
Author = {Bagchi, Uttarayan and Sullivan, Robert S. and Chang, Y. L.},
Journal = {Naval Research Logistics Quarterly},
Number = {2},
Pages = {227--240},
Publisher = {Wiley Subscription Services, Inc., A Wiley Company},
Title = {Minimizing mean absolute deviation of completion times about a common due date},
Volume = {33},
Year = {1986},
Annote = {$1 |w_j=w|\sum{w_j|C_j-d|}$, $d\geq\sum{p_j}$ is in P}}
@article{Weng:96:Unweighted-quadratic-deviation-larger-common-due-date-penalty-function,
Author = {Weng, Xiaohua and Ventura, Jose A},
Journal = {European Journal of Operational Research},
Number = {2},
Pages = {328--335},
Publisher = {Elsevier},
Title = {Scheduling about a given common due date to minimize mean squared deviation of completion times},
Volume = {88},
Year = {1996},
Annote = {$1 |w_j=1|\sum{w_j(C_j-d)^2}$, $d\leq d^{**}$ can be solved in time $O(n \sum_j p_j)$}}
@article{Mondal:02:Unweighted-quadratic-deviation-common-due-date-penalty-function,
Author = {Mondal, Sakib A},
Journal = {Computers \& Operations Research},
Number = {14},
Pages = {2073--2085},
Publisher = {Elsevier},
Title = {Minimization of squared deviation of completion times about a common due date},
Volume = {29},
Year = {2002},
Annote = {$1 |w_j=w|\sum{w_j(C_j-d)^2}$ can be solved in time $O(n^2(d+\max p_j))$}}
@article{SrirangacharyuluSrinivasan:13:Unweighted-squared-deviation-common-due-date-penalty-function,
Author = {B. Srirangacharyulu and G. Srinivasan},
Journal = {European Journal of Operational Research},
Number = {3},
Pages = {547-556},
Title = {An exact algorithm to minimize mean squared deviation of job completion times about a common due date},
Volume = {231},
Year = {2013},
Annote = {$1 |w_j=w|\sum{w_j(C_j-d)^2}$, can be solved in time $O(nd)$}}
@article{BagchiSullivanYih-Long:87:Unweighted-quadratic-deviation-larger-common-due-date-penalty-function,
Author = {Bagchi, Uttarayan and Sullivan, Robert S. and Chang, Yih Long},
Journal = {Management Science},
Number = {7},
Pages = {894-906},
Title = {Minimizing Mean Squared Deviation of Completion Times About a Common Due Date},
Volume = {33},
Year = {1987},
Annote = {$1 ||\sum{w_j(C_j-d)^2}$, $d\geq\sum{p_j}$ is binary $NP$-hard}}
@article{Kubiak:93:Unweighted-quadratic-deviation-larger-common-due-date-penalty-function,
Author = {Kubiak, W.},
Journal = {Operations Research Letters},
Number = {1},
Pages = {49--59},
Publisher = {Elsevier},
Title = {Completion time variance minimization on a single machine is difficult},
Volume = {14},
Year = {1993},
Annote = {$1 |w_j=w|\sum{w_j(C_j-d)^2}$, $d\geq d*$ is binary $NP$-hard}}
@inproceedings{CheungShmoys:11:Approach-primal-dual-scheduling-penaty-function-of-jobs,
Author = {Cheung, M. and Shmoys, D.},
Booktitle = {Proc. of the 14th International Workshop APPROX and 15th International Workshop RANDOM},
Pages = {135--146},
Title = {A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems},
Year = {2011},
Annote = {$1 ||\sum_j{f(C_j)}$, has a $2+\varespilon$ algorithm}}
@inproceedings{BansalPruhs:10:Approach-geometry-scheduling-penalty-function-of-jobs,
Author = {Bansal, N. and Pruhs, K.},
Booktitle = {Proc. of the IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)},
Pages = {407--414},
Title = {The Geometry of Scheduling},
Year = {2010},
Annote = {$1 ||\sum_j{f(C_j)}$, has a 16 algorithm}}
@article{EpsteinLevin:10:Approach-adversary-scheduling-weighted-penalty-function-of-jobsUniversal-sequencing,
Author = {Epstein, L. and Levin, A. and Marchetti-Spaccamela, A. and Megow, N. and Mestre, J. and Skutella, M. and Stougie, L.},
Date-Added = {2012-04-17 12:10:03 +0000},
Date-Modified = {2012-04-17 12:16:48 +0000},
Journal = {In Proc. of the 14th International Conference of Integer Programming and Combinatorial Optimization (IPCO)},
Pages = {230--243},
Publisher = {Springer},
Title = {Universal sequencing on a single machine},
Year = {2010},
Annote = {$1 ||\sum_j{w_jf(C_j)}$, has a $2+\varespilon$ algorithm}}
@unpublished{Vasquez:13:Survey,
Author = {Oscar C. V{\'a}squez},
Note = {manuscript},
Title = {On the complexity of the single machine scheduling problem minimizing total weighted delay penalty},
Year = {2013}}
@inproceedings{DurrVasquez:13:Rules,
Author = {Christoph D\"urr and Oscar C. V\'asquez},
Booktitle = {Proc. of the 16th Workshop on Algorithm Engineering and Experiments (ALENEX)},
Pages = {98-111},
Title = {Order constraints for single machine scheduling with non-linear cost},
Year = {2014}}
@inproceedings{DurrJezVasquez:13:Marginal-Game,
Author = {Christoph D\"urr and {\L}ukasz Je{\.z} and Oscar C. V\'asquez},
Booktitle = {Proc. of the 9th Conference on Web and Internet Economics (WINE)},
Pages = {134-145},
Title = {Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling},
Year = 2013}
@techreport{Vasquez:12:Optimization-Mechanism,
Author = {Oscar C. Vasquez},
Institution = {Arxiv.org},
Number = {arXiv:1212.6375},
Title = {Energy in computing systems with speed scaling: optimization and mechanisms design},
Year = {2012}}
@article{Brooks:00:Alpha-coefficient-value,
Author = {Brooks, David M and Bose, Pradip and Schuster, Stanley E and Jacobson, Hans and Kudva, Prabhakar N and Buyuktosunoglu, Alper and Wellman, J and Zyuban, Victor and Gupta, Manish and Cook, Peter W},
Journal = {Micro, IEEE},
Number = {6},
Pages = {26--44},
Publisher = {IEEE},
Title = {Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors},
Volume = {20},
Year = {2000}}
@article{Albers:10:Survey-energy-management,
Author = {Albers, S.},
Date-Added = {2013-10-10 18:33:26 +0000},
Date-Modified = {2013-10-10 18:33:26 +0000},
Journal = {Communications of the ACM},
Number = {5},
Pages = {86--96},
Publisher = {ACM},
Title = {Energy-efficient algorithms},
Volume = {53},
Year = {2010}}
@article{LiLiuYao:06:Energy-Minimization-Tree,
Author = {M.Li and B.J. Liu and F.F. Yao},
Journal = {Journal of Combinatorial Optimization},
Number = {3},
Pages = {305-319},
Title = {Min-energy voltage allocation for tree-structured tasks},
Volume = {11},
Year = {2006},
Annote = {$SpeedScaling;1 |prec=tree;r_j;|E$ can be solved in time $O(n^2)$}}
@inproceedings{YaoDemmersShenker:95:Energy-minimization,
Author = {Yao, F. and Demers, A. and Shenker, S.},
Booktitle = {Proc. of the 36th Annual Symposium on Foundations of Computer Science (FOCS)},
Pages = {374-382},
Title = {A scheduling model for reduced CPU energy},
Year = 1995,
Annote = {$1 ||E(C_j)$ is in P}}
@article{LiAndrewYaoYao:06:Energy-minimization,
Author = {M Li and Andrew C. Yao and Frances F. Yao},
Booktitle = {Proc. of the National Academy of Sciences of the United States of America},
Number = {11},
Pages = {3983-3987},
Title = {Discrete and Continuous Min-Energy Schedules for Variable Voltage Processor},
Volume = {103},
Year = {2006},
Annote = {$SpeedScaling;1|r_j|E$ can be solved in time $O(n^2\log n)$}}
@misc{Durr:13:Scheduling-zoo,
Author = {Christoph D\"urr},
Howpublished = {``http://www-desir.lip6.fr/~durrc/query/''},
Title = {Scheduling Zoo},
Year = 2013}
@article{MondererShapley:96:Potential-games,
Author = {D. Monderer and L.S. Shapley},
Date-Modified = {2013-02-18 17:00:56 +0000},
Journal = {Games and Economic Behavior},
Pages = {124--143},
Title = {Potential Games},
Volume = 14,
Year = 1996}
@article{MoulinShenker:01:Strategyproof-sharing-submodular,
Author = {Moulin, H. and Shenker, S.},
Date-Added = {2013-02-18 16:37:35 +0000},
Date-Modified = {2013-02-18 16:37:50 +0000},
Journal = {Economic Theory},
Number = {3},
Pages = {511--533},
Publisher = {Springer},
Title = {Strategyproof sharing of submodular costs: budget balance versus efficiency},
Volume = {18},
Year = {2001}}
@article{BansalKimbrelPruhs:07:Proof-optimality-YDS-KKT,
Author = {Bansal, Nikhil and Kimbrel, Tracy and Pruhs, Kirk},
Journal = {Journal of the ACM (JACM)},
Number = {1},
Pages = {3},
Publisher = {ACM},
Title = {Speed scaling to manage energy and temperature},
Volume = {54},
Year = {2007}}
@article{IraniPruhs:05:Problems-energy-management,
Author = {Irani, S. and Pruhs, K.R.},
Date-Added = {2013-10-10 18:33:26 +0000},
Date-Modified = {2013-10-10 18:33:26 +0000},
Journal = {ACM SIGACT News},
Number = {2},
Pages = {63--76},
Publisher = {ACM},
Title = {Algorithmic problems in power management},
Volume = {36},
Year = {2005}}
@article{AlbersFujiwara:07:Some-minimization-energy-QoS,
Author = {Albers, Susanne and Fujiwara, Hiroshi},
Date-Added = {2013-10-10 18:31:19 +0000},
Date-Modified = {2013-10-10 18:31:19 +0000},
Journal = {ACM Transactions on Algorithms (TALG)},
Number = {4},
Pages = {49},
Publisher = {ACM},
Title = {Energy-efficient algorithms for flow time minimization},
Volume = {3},
Year = {2007}}
@inproceedings{AngelBampisKacem:12:Parallel-unrelated-machine-scheduling-energy,
Author = {Angel, Eric and Bampis, Evripidis and Kacem, Fadi},
Booktitle = {Proc. of the IEEE International Conference on Green Computing and Communications (GreenCom)},
Pages = {533--540},
Title = {Energy Aware Scheduling for Unrelated Parallel Machines},
Year = {2012}}
@article{BansalChanKatzPruhs:12:Some-minimization-energy-QoS,
Author = {Bansal, Nikhil and Chan, Ho Leung and Katz, D and Pruhs, Kirk},
Date-Modified = {2015-12-11 16:58:14 +0000},
Journal = {Theory of Computing},
Pages = {209--229},
Title = {Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule},
Volume = {8},
Year = {2012}}
@techreport{CarrascoIyegarStein:11:Some-minimization-energy-QoS,
Annotate = {presented at the 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)},
Author = {Rodrigo A. Carrasco and Garud Iyengar and Clifford Stein},
Institution = {arxiv.org},
Number = {arXiv:1110.0685},
Title = {Energy Aware Scheduling for Weighted Completion Time and Weighted Tardiness},
Year = 2011}
@inproceedings{ChanLamLee:10:Some-minimization-energy-QoS,
Author = {Chan, Sze Hang and Lam, Tak Wah and Lee, Lap Kei},
Booktitle = {Proc. of the 18th Annual European Symposium (ESA)},
Pages = {23--35},
Title = {Non-clairvoyant speed scaling for weighted flow time},
Year = {2010}}
@article{PruhsUthaisombutWoeginger:08:Minimization-unweighted-completion-time-constraint-energy,
Author = {Pruhs, Kirk and Uthaisombut, Patchrawat and Woeginger, Gerhard},
Journal = {ACM Transactions on Algorithms (TALG)},
Number = {3},
Pages = {38},
Publisher = {ACM},
Title = {Getting the best response for your erg},
Volume = {4},
Year = {2008}}
@inproceedings{AngelBampisChauLetsios:13:Minimization-energy-number-jobs,
Author = {Angel, Eric and Bampis, Evripidis and Chau, Vincent and Letsios, Dimitrios},
Booktitle = {Proc. of the 10th International Conference of Theory and Applications of Models of Computation},
Pages = {10--19},
Title = {Throughput Maximization for Speed-Scaling with Agreeable Deadlines},
Year = {2013}}
@article{SchildFredman:62:Order-constraint-quadratic-penalty-function-with-t*,
Author = {Schild, A. and Fredman, I.J.},
Journal = {Management Science},
Number = {1},
Pages = {73--81},
Publisher = {INFORMS},
Title = {Scheduling tasks with deadlines and non-linear loss functions},
Volume = {9},
Year = {1962}}