{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:16:22Z","timestamp":1787508982101,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540343752","type":"print"},{"value":"9783540343783","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758471_20","type":"book-chapter","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T06:34:15Z","timestamp":1149230055000},"page":"187-198","source":"Crossref","is-referenced-by-count":6,"title":["Tighter Approximation Bounds for LPT Scheduling in Two Special Cases"],"prefix":"10.1007","author":[{"given":"Annam\u00e1ria","family":"Kov\u00e1cs","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, \u00c9.: Truthful mechanisms for one-parameter agents. In: Proc. 42nd IEEE Symp. on Found. of Comp. Sci (FOCS), pp. 482\u2013491 (2001)","DOI":"10.1109\/SFCS.2001.959924"},{"issue":"1","key":"20_CR2","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y. Cho","year":"1980","unstructured":"Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM Journal on Computing\u00a09(1), 91\u2013103 (1980)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"20_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0207001","volume":"7","author":"E.G. Coffman","year":"1978","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S.: An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing\u00a07(1), 1\u201317 (1978)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"20_CR4","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1137\/0213044","volume":"13","author":"G. Dobson","year":"1984","unstructured":"Dobson, G.: Scheduling independent tasks on uniform processors. SIAM Journal on Computing\u00a013(4), 705\u2013716 (1984)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"20_CR5","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1137\/0216037","volume":"16","author":"D.K. Friesen","year":"1987","unstructured":"Friesen, D.K.: Tighter bounds for LPT scheduling on uniform processors. SIAM Journal on Computing\u00a016(3), 554\u2013560 (1987)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"20_CR6","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1137\/0206013","volume":"6","author":"T. Gonzalez","year":"1977","unstructured":"Gonzalez, T., Ibarra, O.H., Sahni, S.: Bounds for LPT schedules on uniform processors. SIAM Journal on Computing\u00a06(1), 155\u2013166 (1977)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"20_CR7","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D.S. Hochbaum","year":"1988","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM J. Comp.\u00a017(3), 539\u2013551 (1988)","journal-title":"SIAM J. Comp."},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM\u00a023, 317\u2013327 (1976)","journal-title":"Journal of the ACM"},{"key":"20_CR9","unstructured":"Kov\u00e1cs, A.: Tighter approximation bounds for LPT scheduling in two special cases, Extended version: \n                    \n                      http:\/\/www.mpi-inf.mpg.de\/~panni\/approx.ps"},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1007\/11561071_55","volume-title":"Algorithms \u2013 ESA 2005","author":"A. Kov\u00e1cs","year":"2005","unstructured":"Kov\u00e1cs, A.: Fast monotone 3-approximation algorithm for scheduling related machines. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 616\u2013627. Springer, Heidelberg (2005)"},{"issue":"2","key":"20_CR11","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1137\/S0097539799527969","volume":"27","author":"R. Li","year":"1998","unstructured":"Li, R., Shi, L.: An on-line algorithm for some uniform processor scheduling. SIAM Journal on Computing\u00a027(2), 414\u2013422 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR12","unstructured":"Liu, J.W.S., Liu, C.L.: Bounds on scheduling algorithms for heterogeneous computing systems. In: Proc. Intern. Feder. of Inf. Proc. Soc, pp. 349\u2013353 (1974)"},{"issue":"1","key":"20_CR13","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1287\/opre.45.1.116","volume":"45","author":"P. Mireault","year":"1997","unstructured":"Mireault, P., Orlin, J.B., Vohra, R.V.: A parametric worst case analysis of the LPT heuristic for two uniform machines. Oper. Res.\u00a045(1), 116\u2013125 (1997)","journal-title":"Oper. Res."},{"key":"20_CR14","volume-title":"Computers and Intractability; A Guide to the Theory of NP-completeness","author":"D.S. Johnson","year":"1979","unstructured":"Johnson, D.S., Garey, M.R.: Computers and Intractability; A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-540-24749-4_53","volume-title":"STACS 2004","author":"V. Auletta","year":"2004","unstructured":"Auletta, V., De Prisco, R., Penna, P., Persiano, G.: Deterministic truthful approximation mechanisms for scheduling related machines. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 608\u2013619. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758471_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:04:21Z","timestamp":1619492661000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758471_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343752","9783540343783"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11758471_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}