{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T17:35:29Z","timestamp":1773509729759,"version":"3.50.1"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319559100","type":"print"},{"value":"9783319559117","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-55911-7_28","type":"book-chapter","created":{"date-parts":[[2017,3,20]],"date-time":"2017-03-20T10:23:37Z","timestamp":1490005417000},"page":"389-400","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["An $$O(n^2)$$ Algorithm for Computing Optimal Continuous Voltage Schedules"],"prefix":"10.1007","author":[{"given":"Minming","family":"Li","sequence":"first","affiliation":[]},{"given":"Frances F.","family":"Yao","sequence":"additional","affiliation":[]},{"given":"Hao","family":"Yuan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,21]]},"reference":[{"issue":"1","key":"28_CR1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1735223.1735245","volume":"53","author":"S Albers","year":"2010","unstructured":"Albers, S.: Energy-efficient algorithms. Commun. ACM 53(1), 86\u201396 (2010)","journal-title":"Commun. ACM"},{"key":"28_CR2","unstructured":"Albers, S.: Algorithms for dynamic speed scaling. In: STACS 2011, pp. 1\u201311 (2011)"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Albers, S., Antoniadis, A.: Race to idle: new algorithms for speed scaling with a sleep state. In: SODA 2012, pp. 1266\u20131285 (2012)","DOI":"10.1137\/1.9781611973099.100"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: FOCS 1998: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 534\u2013544 (1998)","DOI":"10.1109\/SFCS.1998.743504"},{"key":"28_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-540-78773-0_21","volume-title":"LATIN 2008: Theoretical Informatics","author":"N Bansal","year":"2008","unstructured":"Bansal, N., Bunde, D.P., Chan, H.-L., Pruhs, K.: Average rate speed scaling. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 240\u2013251. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-78773-0_21"},{"key":"28_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-540-70575-8_34","volume-title":"Automata, Languages and Programming","author":"N Bansal","year":"2008","unstructured":"Bansal, N., Chan, H.-L., Lam, T.-W., Lee, L.-K.: Scheduling for speed bounded processors. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 409\u2013420. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-70575-8_34"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, N., Kimbrel, T., Pruhs, K.: Dynamic speed scaling to manage energy and temperature. In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science, pp. 520\u2013529 (2004)","DOI":"10.1109\/FOCS.2004.24"},{"issue":"2","key":"28_CR8","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/202840.202846","volume":"26","author":"AM Ben-Amram","year":"1995","unstructured":"Ben-Amram, A.M.: What is a \u201cpointer machine\u201d? SIGACT News 26(2), 88\u201395 (1995)","journal-title":"SIGACT News"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Bunde, D.P.: Power-aware scheduling for makespan and flow. In: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 190\u2013196 (2006)","DOI":"10.1145\/1148109.1148140"},{"key":"28_CR10","unstructured":"Chan, H.L., Chan, W.T., Lam, T.W., Lee, L.K., Mak, K.S., Wong, P.W.H.: Energy efficient online deadline scheduling. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 795\u2013804 (2007)"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Chan, W.T., Lam, T.W., Mak, K.S., Wong, P.W.H.: Online deadline scheduling with bounded energy efficiency. In: Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation, pp. 416\u2013427 (2007)","DOI":"10.1007\/978-3-540-72504-6_38"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. In: STOC 1983: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 246\u2013251. ACM, New York (1983)","DOI":"10.1145\/800061.808753"},{"key":"28_CR13","unstructured":"Hong, I., Qu, G., Potkonjak, M., Srivastavas, M.B.: Synthesis techniques for low-power hard real-time systems on variable voltage processors. In: Proceedings of the IEEE Real-Time Systems Symposium, pp. 178\u2013187 (1998)"},{"issue":"4","key":"28_CR14","doi-asserted-by":"crossref","first-page":"41:1","DOI":"10.1145\/1290672.1290678","volume":"3","author":"S Irani","year":"2007","unstructured":"Irani, S., Gupta, R.K., Shukla, S.: Algorithms for power savings. ACM Trans. Algorithms 3(4), 41:1\u201341:23 (2007)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"28_CR15","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/1067309.1067324","volume":"36","author":"S Irani","year":"2005","unstructured":"Irani, S., Pruhs, K.: Algorithmic problems in power management. ACM SIGACT News 36(2), 63\u201376 (2005)","journal-title":"ACM SIGACT News"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"Ishihara, T., Yasuura, H.: Voltage scheduling problem for dynamically variable voltage processors. In: Proceedings of International Symposium on Low Power Electronics and Design, pp. 197\u2013202 (1998)","DOI":"10.1145\/280756.280894"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Kwon, W., Kim, T.: Optimal voltage allocation techniques for dynamically variable voltage processors. In: Proceedings of the 40th Conference on Design Automation, pp. 125\u2013130 (2003)","DOI":"10.1145\/775832.775867"},{"key":"28_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/978-3-540-77120-3_42","volume-title":"Algorithms and Computation","author":"T-W Lam","year":"2007","unstructured":"Lam, T.-W., Lee, L.-K., To, I.K.K., Wong, P.W.H.: Energy efficient deadline scheduling in two processor systems. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 476\u2013487. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-77120-3_42"},{"issue":"3","key":"28_CR19","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/050629434","volume":"35","author":"M Li","year":"2005","unstructured":"Li, M., Yao, F.F.: An efficient algorithm for computing optimal discrete voltage schedules. SIAM J. Comput. 35(3), 658\u2013671 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"28_CR20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/s10878-006-7910-6","volume":"11","author":"M Li","year":"2006","unstructured":"Li, M., Liu, B.J., Yao, F.F.: Min-energy voltage allocation for tree-structured tasks. J. Comb. Optim. 11(3), 305\u2013319 (2006)","journal-title":"J. Comb. Optim."},{"issue":"11","key":"28_CR21","doi-asserted-by":"crossref","first-page":"3983","DOI":"10.1073\/pnas.0510886103","volume":"103","author":"M Li","year":"2006","unstructured":"Li, M., Yao, A.C., Yao, F.F.: Discrete and continuous min-energy schedules for variable voltage processors. Proc. Nat. Acad. Sci. USA 103(11), 3983\u20133987 (2006)","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"28_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/978-3-642-15369-3_27","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"K Pruhs","year":"2010","unstructured":"Pruhs, K., Stein, C.: How to schedule when you have to buy your energy. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX\/RANDOM 2010. LNCS, vol. 6302, pp. 352\u2013365. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-15369-3_27"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"Pruhs, K., Uthaisombut, P., Woeginger, G.: Getting the best response for your erg. In: Scandanavian Workshop on Algorithms and Theory, pp. 14\u201325 (2004)","DOI":"10.1007\/978-3-540-27810-8_3"},{"issue":"2","key":"28_CR24","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215\u2013225 (1975)","journal-title":"J. ACM"},{"issue":"12\u201314","key":"28_CR25","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1016\/j.tcs.2010.12.013","volume":"412","author":"W Wu","year":"2011","unstructured":"Wu, W., Li, M., Chen, E.: Min-energy scheduling for aligned jobs in accelerate model. Theor. Comput. Sci. 412(12\u201314), 1122\u20131139 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"28_CR26","doi-asserted-by":"crossref","unstructured":"Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced CPU energy. In: Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pp. 374\u2013382 (1995)","DOI":"10.1109\/SFCS.1995.492493"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-55911-7_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T20:20:11Z","timestamp":1568924411000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-55911-7_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319559100","9783319559117"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-55911-7_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}