{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:27:26Z","timestamp":1725496046032},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770497"},{"type":"electronic","value":"9783540770503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77050-3_7","type":"book-chapter","created":{"date-parts":[[2007,11,26]],"date-time":"2007-11-26T08:39:22Z","timestamp":1196066362000},"page":"84-95","source":"Crossref","is-referenced-by-count":3,"title":["\u201cRent-or-Buy\u201d Scheduling and Cost Coloring Problems"],"prefix":"10.1007","author":[{"given":"Takuro","family":"Fukunaga","sequence":"first","affiliation":[]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"E.M. Arkin","year":"1987","unstructured":"Arkin, E.M., Silverberg, E.B.: Scheduling jobs with fixed start and end times. Disc. Applied Math.\u00a018, 1\u20138 (1987)","journal-title":"Disc. Applied Math."},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0304-3975(95)00057-4","volume":"148","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., Jansen, K.: Restrictions of graph partition problems. Part I. Theoretical Computer Science\u00a0148, 93\u2013109 (1995)","journal-title":"Theoretical Computer Science"},{"key":"7_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/11602613_82","volume-title":"Algorithms and Computation","author":"J. Cardinal","year":"2005","unstructured":"Cardinal, J., Fiorini, S., Joret, G.: Minimum entropy coloring. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 819\u2013828. Springer, Heidelberg (2005)"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/11424925_23","volume-title":"Computational Science and Its Applications \u2013 ICCSA 2005","author":"F. Croce Della","year":"2005","unstructured":"Della Croce, F., Escoffier, B., Murat, C., Paschos, V.T.: Probabilistic coloring of bipartite and split graphs. In: Gervasi, O., Gavrilova, M., Kumar, V., Lagan\u00e0, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol.\u00a03480, pp. 202\u2013211. Springer, Heidelberg (2005)"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/11830924_13","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"L. Epstein","year":"2006","unstructured":"Epstein, L., Halld\u00f3rsson, M.M., Levin, A., Shachnai, H.: Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 116\u2013127. Springer, Heidelberg (2006)"},{"issue":"3","key":"7_CR6","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.ipl.2005.09.013","volume":"97","author":"B. Escoffier","year":"2006","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T.: Weighted Coloring: Further complexity and approximability results. Inf. Process. Lett.\u00a097(3), 98\u2013103 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"7_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1137\/S089548010240415X","volume":"18","author":"U. Feige","year":"2004","unstructured":"Feige, U.: Approximating Maximum Clique by Removing Subgraphs. SIAM J. Discrete Math.\u00a018(2), 219\u2013225 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR8","first-page":"187","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. JCSS\u00a057, 187\u2013199 (1998)","journal-title":"JCSS"},{"issue":"5","key":"7_CR9","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0020-0190(02)00288-0","volume":"84","author":"F.V. Fomin","year":"2002","unstructured":"Fomin, F.V., Kratsch, D., Novelli, J.-C.: Approximating minimum cocolorings. Inf. Process. Lett.\u00a084(5), 285\u2013290 (2002)","journal-title":"Inf. Process. Lett."},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/0095-8956(80)90079-9","volume":"29","author":"A. Frank","year":"1980","unstructured":"Frank, A.: On chain and antichain families of a partially ordered set. Journal of Combinatorial Theory Series B\u00a029, 176\u2013184 (1980)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"7_CR11","unstructured":"Fukunaga, T., Halld\u00f3rsson, M.M., Nagamochi, H.: Robust cost colorings. In: SODA (2008)"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Gijswijt, D., Jost, V., Queyranne, M.: Clique partitioning of interval graphs with submodular costs on the cliques. EGRES TR 2006-14, www.cs.elte.hu\/egres","DOI":"10.1051\/ro:2007024"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: A still better performance guarantee for approximate graph coloring. Inform. Process. Lett.\u00a045, 19\u201323 (1993)","journal-title":"Inform. Process. Lett."},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00453-003-1031-8","volume":"37","author":"M.M. Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson, M.M., Kortsarz, G., Shachnai, H.: Sum coloring interval and k-claw free graphs with application to scheduling dependent jobs. Algorithmica\u00a037, 187\u2013209 (2003)","journal-title":"Algorithmica"},{"key":"7_CR15","volume-title":"Network Flow, Transportation, and Scheduling: Theory and Algorithms","author":"M. Iri","year":"1969","unstructured":"Iri, M.: Network Flow, Transportation, and Scheduling: Theory and Algorithms. Academic Press, London (1969)"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1006\/jagm.1999.1022","volume":"34","author":"K. Jansen","year":"2000","unstructured":"Jansen, K.: Approximation Results for the Optimum Cost Chromatic Partition Problem. J. Algorithms\u00a034, 54\u201389 (2000)","journal-title":"J. Algorithms"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1016\/j.dam.2005.06.007","volume":"154","author":"C. Murat","year":"2006","unstructured":"Murat, C., Paschos, V.Th.: On the probabilistic minimum coloring and minimum k-coloring. Disc. Appl. Math.\u00a0154, 564\u2013586 (2006)","journal-title":"Disc. Appl. Math."},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"S.V. Pemmaraju","year":"2005","unstructured":"Pemmaraju, S.V., Raman, R.: Approximation Algorithms for the Max-coloring Problem. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, Springer, Heidelberg (2005)"},{"issue":"12","key":"7_CR19","doi-asserted-by":"publisher","first-page":"1477","DOI":"10.1080\/00207160310001614972","volume":"80","author":"A. Saha","year":"2003","unstructured":"Saha, A., Pal, M.: Maximum weight k-independent set problem on permutation graphs. Int. J. Comput. Math.\u00a080(12), 1477\u20131487 (2003)","journal-title":"Int. J. Comput. Math."},{"issue":"2","key":"7_CR20","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M. Yannakakis","year":"1987","unstructured":"Yannakakis, M., Gavril, F.: The maximum k-colorable subgraph problem for chordal graphs. Information Processing Letters\u00a024(2), 133\u2013137 (1987)","journal-title":"Information Processing Letters"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: STOC, pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77050-3_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T22:48:34Z","timestamp":1684104514000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77050-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540770497","9783540770503"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77050-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}