{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T10:40:15Z","timestamp":1742380815659},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540647362"},{"type":"electronic","value":"9783540690672"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0053973","type":"book-chapter","created":{"date-parts":[[2006,7,26]],"date-time":"2006-07-26T17:42:59Z","timestamp":1153935779000},"page":"169-180","source":"Crossref","is-referenced-by-count":8,"title":["Approximating an interval scheduling problem"],"prefix":"10.1007","author":[{"given":"Frits C. R.","family":"Spieksma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,25]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C, Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. Proceedings of the 33rd IEEE Symposium on the Foundations of Computer Science (1992) 14\u201323","DOI":"10.1109\/SFCS.1992.267823"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0166-218X(93)E0174-W","volume":"59","author":"M.C. Carlisle","year":"1995","unstructured":"Carlisle, M.C., Lloyd, E.L.: On the k-coloring of intervals. Discrete Applied Mathematics 59 (1995) 225\u2013235","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR3","doi-asserted-by":"crossref","first-page":"S28","DOI":"10.1287\/opre.40.1.S28","volume":"40","author":"M.W. Carter","year":"1992","unstructured":"Carter, M.W., Tovey, C.A.: When is the classroom assignment problem hard? Operations Research 40 (1992) S28\u2013S39","journal-title":"Operations Research"},{"key":"15_CR4","unstructured":"Crescenzi, P., Kann, V.: A compendium of NP optimization problems, http:\/\/www.nada.kth.se\/nada\/~viggo\/problemlist\/compendium.html"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0166-218X(95)00112-5","volume":"58","author":"U. Faigle","year":"1995","unstructured":"Faigle, U., Nawijn, W.M.: Note on scheduling intervals on-line. Discrete Applied Mathematics 58 (1995) 13\u201317","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR6","doi-asserted-by":"crossref","first-page":"S96","DOI":"10.1287\/opre.40.1.S96","volume":"40","author":"M. Fischetti","year":"1992","unstructured":"Fischetti, M., Martello, S., Toth, P.: Approximation algorithms for fixed job schedule problems. Operations Research 40 (1992) S96\u2013S108","journal-title":"Operations Research"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoretical Computer Science 1 (1976) 237\u2013267","journal-title":"Theoretical Computer Science"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Hoogeveen, J.A., Schuurman, P., Woeginger, G.J.: Non-approximability results for scheduling problems with minsum criteria. Eindhoven University of Technology, COSOR Memorandum 97-24, to appear in the Proceedings of the 6th IPCO Conference, Houston.","DOI":"10.1007\/3-540-69346-7_27"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0167-6377(92)90087-J","volume":"12","author":"J.M. Keil","year":"1992","unstructured":"Keil, J.M.: On the complexity of scheduling tasks with discrete starting times. Operations Research Letters 12 (1992) 293\u2013295","journal-title":"Operations Research Letters"},{"key":"15_CR10","unstructured":"Kolen, A.W.J., personal communication."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1287\/opre.45.4.624","volume":"45","author":"L.G. Kroon","year":"1997","unstructured":"Kroon, L.G., Salomon, M., van Wassenhove, L.N.: Exact and approximation algorithms for the tactical fixed interval scheduling problem. Operations Research 45 (1997) 624\u2013638","journal-title":"Operations Research"},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1016\/0196-6774(82)90030-X","volume":"3","author":"K. Nakajima","year":"1982","unstructured":"Nakajima, K., Hakimi, S.L.: Complexity results for scheduling tasks with discrete starting times. Journal of Algorithms 3 (1982) 344\u2013361","journal-title":"Journal of Algorithms"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation and complexity classes. Journal of Computer and System Sciences 43 (1991) 425\u2013440","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0167-5060(08)70395-9","volume":"55","author":"M.D. Plummer","year":"1993","unstructured":"Plummer, M.D.: Matching and vertex packing: how \u201chard\u201d are they? Annals of Discrete Mathematics 55 (1993) 275\u2013312","journal-title":"Annals of Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatiorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0053973","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T10:51:30Z","timestamp":1549882290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0053973"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540647362","9783540690672"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/bfb0053973","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}