{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T11:27:03Z","timestamp":1747654023626,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054353","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"35-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["An approximation scheme for bin packing with conflicts"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(96)00031-X","volume":"162","author":"B.S. Baker","year":"1996","unstructured":"B.S. Baker and E.G. Coffman, Mutual exclusion scheduling, Theoretical Computer Science, 162 (1996) 225\u2013243.","journal-title":"Theoretical Computer Science"},{"key":"4_CR2","first-page":"369","volume-title":"Domain Decomposition Methods in Scientific and Engineering Computing","author":"P. Bjorstad","year":"1995","unstructured":"P. Bjorstad, W.M. Coughran and E. Grosse: Parallel domain decomposition applied to coupled transport equations, in: Domain Decomposition Methods in Scientific and Engineering Computing (eds. D.E. Keys, J. Xu), AMS, Providence, 1995, 369\u2013380."},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender and K. Jansen, On the complexity of scheduling incompatible jobs with unit-times, Mathematical Foundations of Computer Science, MFCS 93, LNCS 711, 291\u2013300.","DOI":"10.1007\/3-540-57182-5_21"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"E.G. Coffman, Jr., M.R. Garey and D.S. Johnson, Approximation algorithms for bin-packing \u2014 a survey, in: Approximation algorithms for NP-hard problems (ed. D.S. Hochbaum), PWS Publishing, 1995, 49\u2013106.","DOI":"10.1007\/978-3-7091-4338-4_3"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Kilian, Zero Knowledge and the chromatic number, Conference on Computational Complexity, CCC 96, 278\u2013287.","DOI":"10.1109\/CCC.1996.507690"},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. F. de la Vega","year":"1981","unstructured":"W. Fernandez de la Vega and G.S. Lueker, Bin packing can be solved within 1 + \u03b5 in linear time, Combinatorial, 1 (1981) 349\u2013355.","journal-title":"Combinatorial"},{"key":"4_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979."},{"key":"4_CR8","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, London, 1980."},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01294263","volume":"11","author":"S. Irani","year":"1994","unstructured":"S. Irani, Coloring inductive graphs on-line, Algorithmica, 11 (1994) 53\u201372.","journal-title":"Algorithmica"},{"key":"4_CR10","unstructured":"S. Irani and V. Leung, Scheduling with conflicts, and applications to traffic signal control, Symposium on Discrete Algorithms, SODA 96, 85\u201394."},{"key":"4_CR11","unstructured":"S. Irani, private communication."},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1006\/inco.1996.2616","volume":"132","author":"K. Jansen","year":"1997","unstructured":"K. Jansen and S. \u00f6hring, Approximation algorithms for time constrained scheduling, Information and Computation, 132 (1997) 85\u2013108.","journal-title":"Information and Computation"},{"key":"4_CR13","first-page":"287","volume":"1373","author":"K. Jansen","year":"1998","unstructured":"K. Jansen, The mutual exclusion scheduling problem for permutation and comparability graphs, Symposium on Theoretical Aspects of Computer Science, STACS 98, LNCS 1373, 1998, 287\u2013297.","journal-title":"LNCS"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"D. Kaller, A. Gupta and T. Shermer: The \u03c7t \u2014 coloring problem, Symposium on Theoretical Aspects of Computer Science, STACS 95, LNCS 900, 409\u2013420.","DOI":"10.1007\/3-540-59042-0_92"},{"key":"4_CR15","unstructured":"N. Karmarkar and R.M. Karp, An efficient approximation scheme for the one-dimensional bin packing problem, Symposium on the Foundations of Computer Science, FOCS 82, 312\u2013320."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Z. Lonc: On complexity of some chain and antichain partition problem, Graph Theoretical Concepts in Computer Science, WG 91, LNCS 570, 97\u2013104.","DOI":"10.1007\/3-540-55121-2_9"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0377-2217(85)90167-5","volume":"19","author":"D. de Werra","year":"1985","unstructured":"D. de Werra, An introduction to timetabling, European Journal of Operations Research, 19 (1985) 151\u2013162.","journal-title":"European Journal of Operations Research"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054353","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:20:37Z","timestamp":1736407237000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054353"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0054353","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"26 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}