{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:54Z","timestamp":1787323554951,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein, and Wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic) approximation guarantee. We improve the approximation guarantee of their work and present further improvements for some important NP-hard special cases of this problem (e.g., in the preemptive case where machines can suspend work on operations and later resume). We also present NC algorithms with improved approximation guarantees for some NP-hard special cases.<\/jats:p>","DOI":"10.1137\/s0895480199326104","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"67-92","source":"Crossref","is-referenced-by-count":37,"title":["Better Approximation Guarantees for Job-Shop Scheduling"],"prefix":"10.1137","volume":"14","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mike","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elizabeth","family":"Sweedyk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523683"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.2.149"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Bar\u2010Noy, R. Canetti, S. Kutten, Y. Mansour, and B. Schieber,\n                      Bandwidth allocation with preemption\n                      , in Proceedings of the 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, ACM, New York, 1995, pp. 616\u2013625.","DOI":"10.1145\/225058.225279"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.35.2.164"},{"key":"R7","unstructured":"P. Erd\u00f6s and L. Lov\u00e1sz,\n                      Problems and results on 3\u2010chromatic hypergraphs and some related questions\n                      , in Infinite and Finite Sets, A. Hajnal, R. Rado, and V. T. S\u00f3s, eds., Colloq. Math. Soc. Janos Bolyai 11, North Holland, Amsterdam, 1975, pp. 609\u2013627."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"U. Feige and C. Scheideler,\n                      Improved bounds for acyclic job shop scheduling\n                      , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, 1998, ACM, New York, 1998, pp. 624\u2013633.","DOI":"10.1145\/276698.276878"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"L. A. Hall,\n                      Approximability of flow shop scheduling\n                      , in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, Milwaukee, WI, 1995, pp. 82\u201391.","DOI":"10.1109\/SFCS.1995.492465"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys,\n                      Sequencing and scheduling: algorithms and complexity\n                      , in Logistics of Production and Inventory, Handbooks Oper. Res. Management Sci., 4, S. C. Graves et al., eds., Elsevier, New York, 1993, pp. 445\u2013522.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050061"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"S. Mahajan, E. A. Ramos, and K. V. Subrahmanyam,\n                      Solving some discrepancy problems in NC\n                      , in Proceedings of the Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Comput. Sci. 1346, Springer, New York, 1997, pp. 22\u201336.","DOI":"10.1007\/BFb0058020"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"PaulMartin, DavidShmoys, A new approach to computing optimal schedules for the job\u2010shop scheduling problem, Lecture Notes in Comput. Sci., Vol. 1084, Springer, Berlin, 1996, 389\u201340398b:90074","DOI":"10.1007\/3-540-61310-2_29"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R16","unstructured":"G. Rayzman,\n                      Approximation Techniques for Job\u2010Shop Scheduling Problems\n                      , M.Sc. Thesis, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel, 1996."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"C. Scheideler,\n                      Universal Routing Strategies for Interconnection Networks\n                      , Lecture Notes in Comput. Sci. 1390, Springer, New York, 1998.","DOI":"10.1007\/BFb0052928"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"R19","first-page":"447","volume":"29","author":"Sevast\u2019yanov S. V.","year":"1984","journal-title":"Soviet Math. Dokl.","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R20","first-page":"74","volume":"22","author":"Sevast\u2019yanov S. V.","year":"1986","journal-title":"Kibernetika"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979222676X"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)80004-N"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.2.288"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480199326104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:08:54Z","timestamp":1787321334000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480199326104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0895480199326104"],"URL":"https:\/\/doi.org\/10.1137\/s0895480199326104","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}