{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T12:46:22Z","timestamp":1773319582912,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540853626","type":"print"},{"value":"9783540853633","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_13","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"153-164","source":"Crossref","is-referenced-by-count":4,"title":["Approximating Single Machine Scheduling with Scenarios"],"prefix":"10.1007","author":[{"given":"Monaldo","family":"Mastrolilli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolaus","family":"Mutsanas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/11809678_45","volume-title":"Computing and Combinatorics","author":"H. Aissi","year":"2006","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Approximating min-max (regret) versions of some polynomial problems. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol.\u00a04112, pp. 428\u2013438. Springer, Heidelberg (2006)"},{"key":"13_CR2","unstructured":"Arora, S., Lund, C.: Hardness of approximations. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems. PWS (1995)"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10107-003-0396-4","volume":"98","author":"D. Bertsimas","year":"2002","unstructured":"Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Programming Series B\u00a098, 49\u201371 (2002)","journal-title":"Programming Series B"},{"key":"13_CR4","volume-title":"Introduction to stochastic programming","author":"J. Birge","year":"1997","unstructured":"Birge, J., Louveaux, F.: Introduction to stochastic programming. Springer, Heidelberg (1997)"},{"issue":"1-2","key":"13_CR5","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0166-218X(98)00143-7","volume":"98","author":"C. Chekuri","year":"1999","unstructured":"Chekuri, C., Motwani, R.: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Applied Mathematics\u00a098(1-2), 29\u201338 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0167-6377(99)00056-5","volume":"25","author":"F.A. Chudak","year":"1999","unstructured":"Chudak, F.A., Hochbaum, D.S.: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Operations Research Letters\u00a025, 199\u2013204 (1999)","journal-title":"Operations Research Letters"},{"issue":"4","key":"13_CR7","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1287\/moor.1050.0158","volume":"30","author":"J.R. Correa","year":"2005","unstructured":"Correa, J.R., Schulz, A.S.: Single machine scheduling with precedence constraints. Mathematics of Operations Research\u00a030(4), 1005\u20131021 (2005); Extended abstract in Proceedings of the 10th Conference on Integer Programming and Combinatorial Optimization (IPCO 2004), pp. 283\u2013297 (2004)","journal-title":"Mathematics of Operations Research"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/780542.780629","volume-title":"STOC 2003: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing","author":"I. Dinur","year":"2003","unstructured":"Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered pcp and the hardness of hypergraph vertex cover. In: STOC 2003: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 595\u2013601. ACM, New York (2003)"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/978-3-540-72792-7_33","volume-title":"Integer Programming and Combinatorial Optimization","author":"U. Feige","year":"2007","unstructured":"Feige, U., Jain, K., Mahdian, M., Mirrokni, V.S.: Robust combinatorial optimization with exponential scenarios. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 439\u2013453. Springer, Heidelberg (2007)"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R. Graham","year":"1979","unstructured":"Graham, R., Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G.: 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":"13_CR11","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"L.A. Hall","year":"1997","unstructured":"Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line algorithms. Mathematics of Operations Research\u00a022, 513\u2013544 (1997)","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"13_CR12","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.orl.2006.09.007","volume":"35","author":"A. Kasperski","year":"2007","unstructured":"Kasperski, A., Zieli\u0144ski, P.: On the existence of an fptas for minmax regret combinatorial optimization problems with interval data. Operations Research Letters\u00a035(4), 525\u2013532 (2007)","journal-title":"Operations Research Letters"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: IEEE Conference on Computational Complexity, p. 25 (2002)","DOI":"10.1145\/510014.510017"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. In: Proc. of 18th IEEE Annual Conference on Computational Complexity (CCC), pp. 379\u2013386 (2003)","DOI":"10.1109\/CCC.2003.1214437"},{"key":"13_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2620-6","volume-title":"Robust Discrete Optimization and Its Applications","author":"P. Kouvelis","year":"1997","unstructured":"Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (1997)"},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"E.L. Lawler","year":"1978","unstructured":"Lawler, E.L.: Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics\u00a02, 75\u201390 (1978)","journal-title":"Annals of Discrete Mathematics"},{"issue":"6","key":"13_CR17","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1287\/opre.51.6.981.24912","volume":"51","author":"F. Margot","year":"2003","unstructured":"Margot, F., Queyranne, M., Wang, Y.: Decompositions, network flows and a precedence constrained single machine scheduling problem. Operations Research\u00a051(6), 981\u2013992 (2003)","journal-title":"Operations Research"},{"key":"13_CR18","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120909","volume":"13","author":"C.N. Potts","year":"1980","unstructured":"Potts, C.N.: An algorithm for the single machine sequencing problem with precedence constraints. Mathematical Programming Study\u00a013, 78\u201387 (1980)","journal-title":"Mathematical Programming Study"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-61310-2_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"A.S. Schulz","year":"1996","unstructured":"Schulz, A.S.: Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol.\u00a01084, pp. 301\u2013315. Springer, Heidelberg (1996)"},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-61310-2_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"A.S. Schulz","year":"1996","unstructured":"Schulz, A.S.: Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol.\u00a01084, pp. 301\u2013315. Springer, Heidelberg (1996)"},{"issue":"5","key":"13_CR21","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<203::AID-JOS26>3.0.CO;2-5","volume":"2","author":"P. Schuurman","year":"1999","unstructured":"Schuurman, P., Woeginger, G.J.: Polynomial time approximation algorithms for machine scheduling: ten open problems. Journal of Scheduling\u00a02(5), 203\u2013213 (1999)","journal-title":"Journal of Scheduling"},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.E. Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single-stage production. Naval Research Logistics Quarterly\u00a03, 59\u201366 (1956)","journal-title":"Naval Research Logistics Quarterly"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:24:13Z","timestamp":1606184653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}