{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T21:27:25Z","timestamp":1772832445322,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,10,28]],"date-time":"2008-10-28T00:00:00Z","timestamp":1225152000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2009,4]]},"DOI":"10.1007\/s10951-008-0089-1","type":"journal-article","created":{"date-parts":[[2008,10,27]],"date-time":"2008-10-27T17:51:01Z","timestamp":1225129861000},"page":"199-224","source":"Crossref","is-referenced-by-count":59,"title":["Scheduling with conflicts: online and offline algorithms"],"prefix":"10.1007","volume":"12","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lotem","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,10,28]]},"reference":[{"key":"89_CR1","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF01956769","volume":"42","author":"N. Alon","year":"1983","unstructured":"Alon, N. (1983). A note on the decomposition of graphs into isomorphic matchings. Acta Mathematica Hungarica, 42, 221\u2013223.","journal-title":"Acta Mathematica Hungarica"},{"issue":"2","key":"89_CR2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0304-3975(96)00031-X","volume":"162","author":"B. S. Baker","year":"1996","unstructured":"Baker,\u00a0B. S., & Coffman, Jr.,\u00a0E. G. (1996). Mutual exclusion scheduling. Theoretical Computer Science, 162(2), 225\u2013243.","journal-title":"Theoretical Computer Science"},{"key":"89_CR3","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1006\/jagm.2000.1106","volume":"37","author":"A. Bar-Noy","year":"2000","unstructured":"Bar-Noy,\u00a0A., Halld\u00f3rsson,\u00a0M. M., Kortsarz,\u00a0G., Salman,\u00a0R., & Shachnai,\u00a0H. (2000). Sum multicoloring of graphs. Journal of Algorithms, 37, 422\u2013450.","journal-title":"Journal of Algorithms"},{"key":"89_CR4","first-page":"291","volume-title":"MFCS\u201993: Proceedings of the 18th international symposium on mathematical foundations of computer science","author":"H. L. Bodlaender","year":"1993","unstructured":"Bodlaender,\u00a0H. L., & Jansen,\u00a0K. (1993). On the complexity of scheduling incompatible jobs with unit-times. In MFCS\u201993: Proceedings of the 18th international symposium on mathematical foundations of computer science (pp. 291\u2013300). London, UK, 1993. Berlin: Springer."},{"key":"89_CR5","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(95)00057-4","volume":"148","author":"H. L. Bodlaender","year":"1995","unstructured":"Bodlaender,\u00a0H. L., & Jansen,\u00a0K. (1995). Restrictions of graph partition problems. Part I. Theoretical Computer Science, 148, 93\u2013109.","journal-title":"Theoretical Computer Science"},{"key":"89_CR6","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0166-218X(94)90009-4","volume":"55","author":"H. L. Bodlaender","year":"1994","unstructured":"Bodlaender,\u00a0H. L., Jansen,\u00a0K., & Woeginger,\u00a0G. J. (1994). Scheduling with incompatible jobs. Discrete Applied Mathematics, 55, 219\u2013232.","journal-title":"Discrete Applied Mathematics"},{"key":"89_CR7","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1137\/S0097539703423941","volume":"33","author":"A. L. Buchsbaum","year":"2004","unstructured":"Buchsbaum,\u00a0A. L., Karloff,\u00a0H., Kenyon,\u00a0C., Reingold,\u00a0N., & Thorup,\u00a0M. (2004). OPT versus LOAD in dynamic storage allocation. SIAM Journal on Computing, 33, 632\u2013646.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"89_CR8","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1137\/0214054","volume":"14","author":"E. G. Coffman Jr.","year":"1985","unstructured":"Coffman, Jr. E. G., Garey,\u00a0M. R., Johnson,\u00a0D. S., & LaPaugh,\u00a0A. S. (1985). Scheduling file transfers. SIAM Journal on Computing, 14(3), 744\u2013780.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"89_CR9","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R. G. Downey","year":"1995","unstructured":"Downey,\u00a0R. G., & Fellows,\u00a0M. R. (1995). Fixed-parameter tractability and completeness i: Basic results. SIAM Journal on Computing, 24(4), 873\u2013921.","journal-title":"SIAM Journal on Computing"},{"key":"89_CR10","doi-asserted-by":"crossref","unstructured":"Duh,\u00a0R., & F\u00fcrer,\u00a0M. (1997). Approximation of k-set cover by semi-local optimization. In Proceedings of the twenty-ninth annual ACM symposium on the theory of computing (pp. 256\u2013264).","DOI":"10.1145\/258533.258599"},{"key":"89_CR11","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0377-2217(96)00123-3","volume":"94","author":"M. Drozdowski","year":"1996","unstructured":"Drozdowski,\u00a0M. (1996). Scheduling multiprocessor tasks\u2014an overview. European Journal of Operational Research, 94, 167\u2013191.","journal-title":"European Journal of Operational Research"},{"key":"89_CR12","unstructured":"Epstein,\u00a0L., & Levin,\u00a0A. (2006). On bin packing with conflicts. In Proceedings of the 4th workshop on approximation and online algorithms (WAOA) (pp. 160\u2013173)."},{"key":"89_CR13","first-page":"187","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige,\u00a0U., & Kilian,\u00a0J. (1998). Zero knowledge and the chromatic number. JCSS, 57, 187\u2013199.","journal-title":"JCSS"},{"key":"89_CR14","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1137\/0204015","volume":"4","author":"M. R. Garey","year":"1975","unstructured":"Garey,\u00a0M. R., & Graham,\u00a0R. L. (1975). Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing, 4, 187\u2013200.","journal-title":"SIAM Journal on Computing"},{"key":"89_CR15","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"M. R. Garey","year":"1975","unstructured":"Garey,\u00a0M. R., & Johnson,\u00a0D. S. (1975). Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing, 4, 397\u2013411.","journal-title":"SIAM Journal on Computing"},{"key":"89_CR16","volume-title":"Computers and intractability","author":"M. R. Garey","year":"1979","unstructured":"Garey,\u00a0M. R., & Johnson,\u00a0D. S. (1979). Computers and intractability. New York: Freeman."},{"issue":"1\u20133","key":"89_CR17","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0012-365X(93)90165-P","volume":"111","author":"P. Hansen","year":"1993","unstructured":"Hansen,\u00a0P., Hertz,\u00a0A., & Kuplinsky,\u00a0J. (1993). Bounded vertex colorings of graphs. Discrete Mathematics, 111(1\u20133), 305\u2013312.","journal-title":"Discrete Mathematics"},{"issue":"2","key":"89_CR18","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0890-5401(02)00032-9","volume":"180","author":"M. M. Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson,\u00a0M. M., Kortsarz,\u00a0G., Proskurowski,\u00a0A., Salman,\u00a0R., Shachnai,\u00a0H., & Telle,\u00a0J. A. (2003). Multicoloring trees. Information and Computation, 180(2), 113\u2013129.","journal-title":"Information and Computation"},{"issue":"3","key":"89_CR19","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1023\/A:1022908509269","volume":"6","author":"S. Irani","year":"2003","unstructured":"Irani,\u00a0S., & Leung,\u00a0V. (2003). Scheduling with conflicts on bipartite and interval graphs. Journal of Scheduling, 6(3), 287\u2013307.","journal-title":"Journal of Scheduling"},{"issue":"4","key":"89_CR20","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1023\/A:1009871302966","volume":"3","author":"K. Jansen","year":"1999","unstructured":"Jansen,\u00a0K. (1999). An approximation scheme for bin packing with conflicts. Journal of Combinatorial Optimization, 3(4), 363\u2013377.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"2","key":"89_CR21","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0890-5401(02)00028-7","volume":"180","author":"K. Jansen","year":"2003","unstructured":"Jansen,\u00a0K. (2003). The mutual exclusion scheduling problem for permutation and comparability graphs. Information and Computation, 180(2), 71\u201381.","journal-title":"Information and Computation"},{"key":"89_CR22","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0196-6774(02)00248-1","volume":"45","author":"K. Jansen","year":"2002","unstructured":"Jansen,\u00a0K., & Porkolab,\u00a0L. (2002). Polynomial time approximation schemes for general multiprocessor job shop scheduling. Journal of Algorithms, 45, 167\u2013191.","journal-title":"Journal of Algorithms"},{"key":"89_CR23","unstructured":"Kaplan,\u00a0L. (2007). Scheduling with conflicts. Master\u2019s thesis, Tel-Aviv University."},{"key":"89_CR24","series-title":"Lecture notes in computer sciences","volume-title":"Symposium on theoretical aspects of computer science, STACS 95","author":"D. Kaller","year":"1995","unstructured":"Kaller,\u00a0D., Gupta,\u00a0A., & Shermer,\u00a0T. (1995). The \u03c7 t coloring problem. In Lecture notes in computer sciences : Vol. 900. Symposium on theoretical aspects of computer science, STACS 95. Berlin: Springer."},{"key":"89_CR25","first-page":"97","volume-title":"WG\u201991: Proceedings of the 17th international workshop","author":"Z. Lonc","year":"1992","unstructured":"Lonc,\u00a0Z. (1992). On complexity of some chain and antichain partition problems. In WG\u201991: Proceedings of the 17th international workshop (pp. 97\u2013104). London, UK, 1992. Berlin: Springer."},{"key":"89_CR26","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"Petrank,\u00a0E. (1994). The hardness of approximation: Gap location. Computational Complexity, 4, 133\u2013157.","journal-title":"Computational Complexity"},{"issue":"6","key":"89_CR27","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1137\/S0097539793248317","volume":"24","author":"D. B. Shmoys","year":"1995","unstructured":"Shmoys,\u00a0D. B., Wein,\u00a0J., & Williamson,\u00a0D. P. (1995). Scheduling parallel machines on-line. SIAM Journal on Computing, 24(6), 1313\u20131331.","journal-title":"SIAM Journal on Computing"},{"key":"89_CR28","doi-asserted-by":"crossref","unstructured":"Zuckerman,\u00a0D. (2006). Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the thirty-sixth annual ACM symposium on the theory of computing (pp. 681\u2013690).","DOI":"10.1145\/1132516.1132612"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-008-0089-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-008-0089-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-008-0089-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T09:39:41Z","timestamp":1559468381000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-008-0089-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,28]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["89"],"URL":"https:\/\/doi.org\/10.1007\/s10951-008-0089-1","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,28]]}}}