{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:40:02Z","timestamp":1738327202513,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540697329"},{"type":"electronic","value":"9783540697336"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69733-6_65","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"661-669","source":"Crossref","is-referenced-by-count":0,"title":["A Lower Bound for the On-Line Preemptive Machine Scheduling with \u2113 p Norm"],"prefix":"10.1007","author":[{"given":"Tianping","family":"Shuai","sequence":"first","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"65_CR1","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation Schemes for Scheduling. In: SODA 1997, pp. 493\u2013500 (1997)"},{"key":"65_CR2","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/s004530010051","volume":"29","author":"A. Avidor","year":"2001","unstructured":"Avidor, A., Azar, Y., Sgall, J.: Ancient and New Algorithms for Load Balancing in the \u2113 p Norm. Algorithmica\u00a029, 422\u2013441 (2001)","journal-title":"Algorithmica"},{"key":"65_CR3","doi-asserted-by":"crossref","unstructured":"Azar, Y., Epstein, A.: Convex programming for Scheduling Unrelated Parallel Machines. In: STOC 2005, pp. 331\u2013337 (2005)","DOI":"10.1145\/1060590.1060639"},{"issue":"2-3","key":"65_CR4","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.tcs.2006.05.016","volume":"361","author":"Y. Azar","year":"2006","unstructured":"Azar, Y., Epstein, A., Epstein, L.: Load Balancing of Temporary Tasks in the \u2113 p Norm. Theoretical Computer Science\u00a0361(2-3), 314\u2013328 (2006)","journal-title":"Theoretical Computer Science"},{"key":"65_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45471-3_30","volume-title":"Algorithm Theory - SWAT 2002","author":"Y. Azar","year":"2002","unstructured":"Azar, Y., Epstein, L., Richter, Y., Woeginger, G.J.: All-Norm Approximation Algorithms. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, pp. 288\u2013297. Springer, Heidelberg (2002)"},{"key":"65_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/978-3-540-27810-8_26","volume-title":"Algorithm Theory - SWAT 2004","author":"Y. Azar","year":"2004","unstructured":"Azar, Y., Taub, S.: All-Norm Approximation for Scheduling on Identical Machines. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 298\u2013310. Springer, Heidelberg (2004)"},{"key":"65_CR7","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1137\/0204021","volume":"1","author":"A.K. Chandra","year":"1975","unstructured":"Chandra, A.K., Wong, C.K.: Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation. SIAM Journal on Computing\u00a01, 249\u2013263 (1975)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"65_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0167-6377(95)00039-9","volume":"18","author":"B. Chen","year":"1995","unstructured":"Chen, B., van Vliet, A., Woeginger, G.J.: An Optimal Algorithm for Preemptive On-Line Scheduling. Operations Research Letters\u00a018(3), 127\u2013131 (1995)","journal-title":"Operations Research Letters"},{"issue":"3","key":"65_CR9","first-page":"345","volume":"1","author":"D.-L. Du","year":"2005","unstructured":"Du, D.-L., Jiang, X., Zhang, G.: Optimal Preemptive Online Scheduling to Minimize \u2113 p Norm on Two Processors. Journal of Manufacturing and Management Optimization\u00a01(3), 345\u2013351 (2005)","journal-title":"Journal of Manufacturing and Management Optimization"},{"key":"65_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/11841036_31","volume-title":"Algorithms \u2013 ESA 2006","author":"T. Ebenlendr","year":"2006","unstructured":"Ebenlendr, T., Jawor, W., Sgall, J.: Preemptive Online Scheduling: Optimal Algorithms for All Speeds. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 327\u2013339. Springer, Heidelberg (2006)"},{"issue":"1","key":"65_CR11","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0167-6377(99)00062-0","volume":"26","author":"L. Epstein","year":"2000","unstructured":"Epstein, L., Sgall, J.: A Lower Bound for On-Line Scheduling on Uniformly Related Machines. Operations Research Letters\u00a026(1), 17\u201322 (2000)","journal-title":"Operations Research Letters"},{"issue":"1","key":"65_CR12","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.jcss.2005.08.002","volume":"72","author":"L. Epstein","year":"2006","unstructured":"Epstein, L., Tassa, T.: Optimal Preemptive Scheduling for General Target Functions. Journal of Computer and System Sciences\u00a072(1), 132\u2013162 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"65_CR13","doi-asserted-by":"crossref","unstructured":"Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: Approximation Algorithms for Scheduling on Multiple Machines. In: FOCS 2005, pp. 254\u2013263 (2005)","DOI":"10.1109\/SFCS.2005.21"},{"key":"65_CR14","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume-title":"Logistics of Production and Inventory","author":"E.L. Lawler","year":"1993","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and Scheduling: Algorithms and Complexity. In: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (eds.) Logistics of Production and Inventory, pp. 445\u2013522. North-Holland, Amsterdam (1993)"},{"issue":"2","key":"65_CR15","first-page":"148","volume":"34","author":"L. Lin","year":"2007","unstructured":"Lin, L.: Semi-Online Scheduling Algorithm under the \u2113 p Norm on Two Identical Machines. Journal of Zhejiang University (Science Edition)\u00a034(2), 148\u2013151 (2007) (in Chinese)","journal-title":"Journal of Zhejiang University (Science Edition)"},{"issue":"1","key":"65_CR16","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1631\/jzus.2005.A0020","volume":"6","author":"L. Lin","year":"2005","unstructured":"Lin, L., Tan, Z.Y., He, Y.: Deterministic and Randomized Scheduling Problems under the \u2113 p Norm on Two Identical Machines. Journal of Zhejiang University Science\u00a06(1), 20\u201326 (2005)","journal-title":"Journal of Zhejiang University Science"},{"issue":"1","key":"65_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R. McNaughton","year":"1959","unstructured":"McNaughton, R.: Scheduling with Deadlines and Loss Functions. Management Science\u00a06(1), 1\u201312 (1959)","journal-title":"Management Science"},{"issue":"1","key":"65_CR18","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ic.2004.10.002","volume":"196","author":"Z. Tan","year":"2005","unstructured":"Tan, Z., He, Y., Epstein, L.: Optimal On-line Algorithms for the Uniform Machine Scheduling Problem with Ordinal Data. Information and Computation\u00a0196(1), 57\u201370 (2005)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69733-6_65.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:03:59Z","timestamp":1738325039000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69733-6_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540697329","9783540697336"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69733-6_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}