{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:38:22Z","timestamp":1776105502041,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642330896","type":"print"},{"value":"9783642330902","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_26","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"289-300","source":"Crossref","is-referenced-by-count":14,"title":["A Model for Minimizing Active Processor Time"],"prefix":"10.1007","author":[{"given":"Jessica","family":"Chang","sequence":"first","affiliation":[]},{"given":"Harold N.","family":"Gabow","sequence":"additional","affiliation":[]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"26_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. CACM\u00a053(5), 86\u201396 (2010)","journal-title":"CACM"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Amur, H., Cipra, J., Gupta, V., Kozuch, M., Ganger, G., Schwan, K.: Robust and flexible power-proportional storage. In: Proceedings of 1st SoCC, pp. 217\u2013218 (2010)","DOI":"10.1145\/1807128.1807164"},{"key":"26_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/978-3-642-14031-0_15","volume-title":"Computing and Combinatorics","author":"M. Babenko","year":"2010","unstructured":"Babenko, M., Gusakov, A., Razenshteyn, I.: Triangle-Free 2-Matchings Revisited. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol.\u00a06196, pp. 120\u2013129. Springer, Heidelberg (2010)"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Baptiste, P.: Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. In: SODA 2006 (2006)","DOI":"10.1145\/1109557.1109598"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Chang, J., Gabow, H.N., Khuller, S.: A Model for Minimizing Active Processor Time (2012), \n                  \n                    http:\/\/www.cs.umd.edu\/~samir\/grant\/active.pdf","DOI":"10.1007\/978-3-642-33090-2_26"},{"issue":"2","key":"26_CR6","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1137\/S0097539703422479","volume":"36","author":"J. Chuzhoy","year":"2006","unstructured":"Chuzhoy, J., Naor, S.: Covering problems with hard capacities. SIAM J. on Computing\u00a036(2), 498\u2013515 (2006)","journal-title":"SIAM J. on Computing"},{"issue":"5","key":"26_CR7","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s10951-010-0176-y","volume":"13","author":"A. Condotta","year":"2010","unstructured":"Condotta, A., Knust, S., Shakhlevich, N.: Parallel batch scheduling of equal-length jobs with release and due dates. J. of Scheduling\u00a013(5), 463\u2013677 (2010)","journal-title":"J. of Scheduling"},{"issue":"2","key":"26_CR8","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0012-365X(80)90002-3","volume":"29","author":"G. Cornu\u00e9jols","year":"1980","unstructured":"Cornu\u00e9jols, G., Pulleyblank, W.: A matching problem with side conditions. Discrete Math.\u00a029(2), 135\u2013159 (1980)","journal-title":"Discrete Math."},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0120901","volume":"13","author":"G. Cornu\u00e9jols","year":"1980","unstructured":"Cornu\u00e9jols, G., Pulleyblank, W.: Perfect triangle-free 2-matchings. Math. Programming Study\u00a013, 1\u20137 (1980)","journal-title":"Math. Programming Study"},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"447","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Canadian J. Math.\u00a017, 447\u2013467 (1965)","journal-title":"Canadian J. Math."},{"issue":"4","key":"26_CR11","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S. Even","year":"1975","unstructured":"Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM J. on Computing\u00a04(4), 507\u2013581 (1975)","journal-title":"SIAM J. on Computing"},{"issue":"3","key":"26_CR12","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/1367064.1367074","volume":"4","author":"G. Even","year":"2008","unstructured":"Even, G., Levi, R., Rawitz, D., Schieber, B., Shahar, S., Sviridenko, M.: Algorithms for capacitated rectangle stabbing and lot sizing with joint set up costs. ACM Trans. on Algorithms\u00a04(3), 34\u201351 (2008)","journal-title":"ACM Trans. on Algorithms"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Flammini, M., Monaco, G., Moscardelli, L., Shachnai, H., Shalom, M., Tamir, T., Zaks, S.: Minimizing total busy time in parallel scheduling with application to optical networks. In: IPDPS Conference, pp. 1\u201312 (2009)","DOI":"10.1109\/IPDPS.2009.5161017"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proc. 15th Annual STOC, pp. 448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"issue":"4","key":"26_CR15","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM\u00a038(4), 815\u2013853 (1991)","journal-title":"J. ACM"},{"issue":"2","key":"26_CR16","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Computer and System Sciences\u00a030(2), 209\u2013221 (1985)","journal-title":"J. Computer and System Sciences"},{"issue":"1","key":"26_CR17","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jcss.2005.06.004","volume":"72","author":"R. Gandhi","year":"2006","unstructured":"Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., Srinivasan, A.: An improved approximation algorithm for vertex cover with hard capacities. J. of Computer and System Sciences\u00a072(1), 16\u201333 (2006)","journal-title":"J. of Computer and System Sciences"},{"issue":"2","key":"26_CR18","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1137\/0210018","volume":"10","author":"M. Garey","year":"1981","unstructured":"Garey, M., Johnson, D., Simons, B., Tarjan, R.: Scheduling unit-time jobs with arbitrary release times and deadlines. SIAM J. on Computing\u00a010(2), 256\u2013269 (1981)","journal-title":"SIAM J. on Computing"},{"issue":"2","key":"26_CR19","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0167-6377(86)90104-5","volume":"5","author":"Y. Ikura","year":"1986","unstructured":"Ikura, Y., Gimple, M.: Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters\u00a05(2), 61\u201365 (1986)","journal-title":"Operations Research Letters"},{"issue":"2","key":"26_CR20","doi-asserted-by":"publisher","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. SIGACT News\u00a036(2), 63\u201376 (2005)","journal-title":"SIGACT News"},{"key":"26_CR21","unstructured":"Khandekar, R., Schieber, B., Shachnai, H., Tamir, T.: Minimizing busy time in multiple machine real-time scheduling. In: FST&TCS Conference, pp. 169\u2013180 (2010)"},{"key":"26_CR22","unstructured":"Koehler, F., Khuller, S.: Quick and efficient: fast algorithms for completion time and batch minimization on multiple machines (manuscript)"},{"issue":"30","key":"26_CR23","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/S0895480197329776","volume":"13","author":"S. Khuller","year":"2000","unstructured":"Khuller, S., Sussman, Y.J.: The capacitated k-center problem. SIAM J. on Discrete Mathematics\u00a013(30), 403\u2013418 (2000)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"26_CR24","unstructured":"Lawler, E.: Combinatorial Optimization. In: Holt, Rinehart and Winston (1976)"},{"key":"26_CR25","unstructured":"L\u00f3pez-Ortiz, A., Quimper, C.-G.: A fast algorithm for multi-machine scheduling problems with jobs of equal processing times. In: Proc. of Symposium on Theoretical Aspects of Computer Science (2011)"},{"key":"26_CR26","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North-Holland (1986)"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum Matchings via Gaussian Elimination. In: FOCS, pp. 248\u2013255 (2004)","DOI":"10.1007\/978-3-540-30140-0_48"},{"issue":"2","key":"26_CR28","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1137\/0212018","volume":"12","author":"B. Simons","year":"1983","unstructured":"Simons, B.: Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. SIAM J. on Computing\u00a012(2), 294\u2013299 (1983)","journal-title":"SIAM J. on Computing"},{"issue":"4","key":"26_CR29","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1137\/0218048","volume":"18","author":"B. Simons","year":"1989","unstructured":"Simons, B., Warmuth, M.: A fast algorithm for multiprocessor scheduling of unit length jobs. SIAM J. on Computing\u00a018(4), 690\u2013710 (1989)","journal-title":"SIAM J. on Computing"},{"issue":"4","key":"26_CR30","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica\u00a02(4), 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:54:50Z","timestamp":1620129290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}