{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:58:39Z","timestamp":1725893919656},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540778905"},{"type":"electronic","value":"9783540778912"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77891-2_17","type":"book-chapter","created":{"date-parts":[[2008,1,12]],"date-time":"2008-01-12T08:19:36Z","timestamp":1200125976000},"page":"180-187","source":"Crossref","is-referenced-by-count":1,"title":["Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs"],"prefix":"10.1007","author":[{"given":"Yerim","family":"Chung","sequence":"first","affiliation":[]},{"given":"Jean-Fran\u00e7ois","family":"Culus","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Demange","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1287\/opre.49.5.771.10607","volume":"49","author":"R.K. Ahuja","year":"2001","unstructured":"Ahuja, R.K., Orlin, J.B.: Inverse optimization. Operations Research\u00a049, 771\u2013783 (2001)","journal-title":"Operations Research"},{"key":"17_CR2","volume-title":"Complexity and approximation (Combinatorial optimization problems and their approximability properties)","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation (Combinatorial optimization problems and their approximability properties). Springer, Heidelberg (1999)"},{"key":"17_CR3","unstructured":"Chung, Y.: On some inverse combinatorial optimization problems. PhD thesis, Paris School of Economics, Paris\u00a0I University (preparation)"},{"key":"17_CR4","unstructured":"Chung, Y., Demange, M.: The 0-1 inverse maximum stable set problem (to be published)"},{"key":"17_CR5","unstructured":"Chung, Y., Demange, M.: Some inverse traveling salesman problems. In: IV Latin-American Algorithms, Graphs and Optimization Symposium (to appear, 2007)"},{"key":"17_CR6","volume-title":"Computers and Intractability \u2013 A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability \u2013 A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"17_CR7","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. Golumbic","year":"1980","unstructured":"Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs. Academic press, New York (1980)"},{"issue":"3","key":"17_CR8","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1023\/B:JOCO.0000038914.26975.9b","volume":"8","author":"C. Heuberger","year":"2004","unstructured":"Heuberger, C.: Inverse combinatorial optimization: A survey on problems, methods, and results. J. Comb. Optim.\u00a08(3), 329\u2013361 (2004)","journal-title":"J. Comb. Optim."},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Kan, A.H.G.R.: Machine scheduling problem: Classification, Complexity and Computation, Nijhoff, The Hague (1976)","DOI":"10.1007\/978-1-4613-4383-7"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1287\/mnsc.11.2.280","volume":"11","author":"E.L. Lawler","year":"1964","unstructured":"Lawler, E.L.: On scheduling problems with deferral costs. Management Sci.\u00a011, 280\u2013288 (1964)","journal-title":"Management Sci."},{"key":"17_CR11","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0167-5060(08)70742-8","volume":"1","author":"E.L. Lawler","year":"1977","unstructured":"Lawler, E.L.: A \u201dpseudopolynomial\u201d algorithm for scheduling jobs to minimize total tardiness. Annals of Discrete Mathematics\u00a01, 331\u2013342 (1977)","journal-title":"Annals of Discrete Mathematics"},{"key":"17_CR12","unstructured":"M\u00fcller-Hannemann, M., Sonnikow, A.: Non-approximability of just-in-time scheduling. Technical report, TU Darmstadt, Extended abstract in MAPSP 2007, Istanbul (2006)"},{"key":"17_CR13","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1287\/moor.13.2.330","volume":"13","author":"R.E. Tarjan","year":"1988","unstructured":"Tarjan, R.E., Garey, M.R., Wilfong, G.T.: One-processor scheduling with symmetric earliness and tardiness penalties. Mathematics of Operations Research\u00a013, 330\u2013348 (1988)","journal-title":"Mathematics of Operations Research"},{"key":"17_CR14","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"J.K. Lenstra","year":"1979","unstructured":"Lenstra, J.K., Graham, R.L., Lawler, E.L., Kan, A.H.G.R.: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics\u00a05, 287\u2013326 (1979)","journal-title":"Annals of Discrete Mathematics"},{"key":"17_CR15","first-page":"930","volume":"23","author":"D. Dessouky","year":"1988","unstructured":"Dessouky, D., Verma, S.: Single-machine scheduling of unit-time jobs with earliness and tardiness penalties. Mathematics of Operations Research\u00a023, 930\u2013943 (1988)","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"17_CR16","first-page":"213","volume":"15","author":"J. Zhang","year":"1999","unstructured":"Zhang, J., Yang, X., Cai, M.-C.: The complexity analysis of the inverse center location problem. J. of Global optimization\u00a015(1), 213\u2013218 (1999)","journal-title":"J. of Global optimization"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77891-2_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:55:05Z","timestamp":1619520905000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77891-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540778905","9783540778912"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77891-2_17","relation":{},"subject":[]}}