{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:57Z","timestamp":1725490257930},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_30","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"338-350","source":"Crossref","is-referenced-by-count":3,"title":["Lower Bounds for On-Line Single-Machine Scheduling"],"prefix":"10.1007","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[]},{"given":"Rob","family":"van Stee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 32\u201343, October 1999.","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"30_CR2","unstructured":"A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna, and A. Zhu. Algorithms for minimizing weighted flow time. In Proc. of the 33th Symp. on Theory of Computing (STOC), 2001.","DOI":"10.1145\/380752.380778"},{"key":"30_CR4","first-page":"609","volume-title":"Proceedings of the Eighth Annual ACMSIAM Symposium on Discrete Algorithms (SODA\u201997)","author":"C. Chekuri","year":"1997","unstructured":"C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. In Proceedings of the Eighth Annual ACMSIAM Symposium on Discrete Algorithms (SODA\u201997), pages 609\u2013618. SIAM, Philadelphia, PA, 1997."},{"key":"30_CR5","unstructured":"M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella, and Y. Wang. Single machine scheduling with release dates. manuscript, 1999."},{"key":"30_CR6","unstructured":"Michel X. Goemans. Improved approximation algorithms for scheduling with release dates. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 591\u2013598, New York \/ Philadelphia, 1997. ACM \/ SIAM."},{"key":"30_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/3-540-61310-2_30","volume-title":"Proc. 5th Int. Conf. Integer Programming and COmbinatorial Optimization","author":"J. A. Hoogeveen","year":"1996","unstructured":"J. A. Hoogeveen and A. P. A. Vestjens. Optimal on-line algorithms for single-machine scheduling. In Proc. 5th Int. Conf. Integer Programming and COmbinatorial Optimization, LNCS, pages 404\u2013414. Springer, 1996."},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"H. Kellerer, T. Tautenhahn, and G. J. Woeginger. Approximability and nonapproximability results for minimizing total flow time on a single machine. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 418\u2013426, Philadelphia, Pennsylvania, 1996.","DOI":"10.1145\/237814.237989"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"J. Labetoulle, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Preemptive scheduling of uniform machines subject to release dates. Progress in Combinatorial Optimization, pages 245\u2013261, 1984.","DOI":"10.1016\/B978-0-12-566780-7.50020-9"},{"key":"30_CR10","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume":"4","author":"E. L. Lawler","year":"1993","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: algorithms and complexity. In Handbooks in operations research and management science, volume 4, pages 445\u2013522. North Holland, 1993.","journal-title":"Handbooks in operations research and management science"},{"key":"30_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/3-540-60220-8_53","volume-title":"Proceedings of the 4th Workshop on Algorithms and Data Structures (WADS\u201995)","author":"C. A. Phillips","year":"1995","unstructured":"C. A. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. In Proceedings of the 4th Workshop on Algorithms and Data Structures (WADS\u201995), volume 955 of Lecture Notes in Computer Science, pages 86\u201397. Springer, 1995."},{"key":"30_CR12","unstructured":"A. S. Schulz and M. Skutella. The power of alpha-points in preemptive single machine scheduling. manuscript, 1999."},{"key":"30_CR13","unstructured":"M. Skutella. personal communication, 2000."},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. E. Smith","year":"1956","unstructured":"W. E. Smith. Various optimizers for single-stage production. Naval Research and Logistics Quarterly, 3:59\u201366, 1956.","journal-title":"Naval Research and Logistics Quarterly"},{"key":"30_CR15","unstructured":"L. Stougie. Unpublished manuscript, 1995."},{"key":"30_CR16","unstructured":"L. Stougie and A. P. A. Vestjens. Randomized on-line scheduling: How low can\u2019t you go? Unpublished manuscript, 1997."},{"key":"30_CR17","series-title":"Ph.D. thesis","volume-title":"Technical report","author":"A. P. A. Vestjens","year":"1997","unstructured":"A. P. A. Vestjens. On-line machine scheduling. Technical report, Ph.D. thesis, Eindhoven University of Technology, The Netherlands, 1997."},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"A. C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. 18th Annual Symposium on Foundations of Computer Science, pages 222\u2013227. IEEE, 1977.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,23]],"date-time":"2019-02-23T06:18:07Z","timestamp":1550902687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_30","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}