{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T23:37:31Z","timestamp":1767137851586,"version":"build-2238731810"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319091730","type":"print"},{"value":"9783319091747","type":"electronic"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09174-7_24","type":"book-chapter","created":{"date-parts":[[2014,7,21]],"date-time":"2014-07-21T01:42:05Z","timestamp":1405906925000},"page":"280-291","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Decomposition Algorithm for the Single Machine Scheduling Polytope"],"prefix":"10.1007","author":[{"given":"Ruben","family":"Hoeksma","sequence":"first","affiliation":[]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Uetz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,7,22]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Cai, Y., Daskalakis, C., Weinberg, S.M.: Optimal multi-dimensional mechanism design: reducing revenue to welfare maximization. In: Proceedings of 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 130\u2013139. IEEE (2012)","DOI":"10.1109\/FOCS.2012.88"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0095-8956(84)90023-6","volume":"36","author":"WH Cunningham","year":"1984","unstructured":"Cunningham, W.H.: Testing membership in matroid polyhedra. J. Comb. Theory B 36, 161\u2013188 (1984)","journal-title":"J. Comb. Theory B"},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/BF02579361","volume":"5","author":"WH Cunningham","year":"1985","unstructured":"Cunningham, W.H.: On submodular function minimization. Combinatorica 5, 186\u2013192 (1985)","journal-title":"Combinatorica"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Fonlupt, J., Skoda, A.: Strongly polynomial algorithm for the intersection of a line with a polymatroid. In: Cook, W., Lov\u00e1sz, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 69\u201385. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-540-76796-1_5"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization: Algorithms and Combinatorics, vol. 2. Springer, Heidelberg (1988)","DOI":"10.1007\/978-3-642-97881-4"},{"key":"24_CR7","unstructured":"Hoeksma, R., Manthey, B., Uetz, M.: Decomposition algorithm for the single machine scheduling polytope. Technical Report TR-CTIT-13-25, CTIT, University of Twente. http:\/\/eprints.eemcs.utwente.nl\/24630\/"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-642-36694-9_21","volume-title":"Integer Programming and Combinatorial Optimization","author":"R Hoeksma","year":"2013","unstructured":"Hoeksma, R., Uetz, M.: Two dimensional optimal mechanism design for a sequencing problem. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 242\u2013253. Springer, Heidelberg (2013)"},{"issue":"4","key":"24_CR9","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial time algorithm for minimizing submodular functions. J. ACM 48(4), 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Lee, C.W.: Subdivisions and triangulations of polytopes. In: Handbook of Discrete and Computational Geometry, chapter 17, 2nd edn. Chapman & Hall\/CRC, Beca Raton (2004)","DOI":"10.1201\/9781420035315.ch17"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/3-540-69346-7_28","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Munier","year":"1998","unstructured":"Munier, A., Queyranne, M., Schulz, A.S.: Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 367\u2013382. Springer, Heidelberg (1998)"},{"key":"24_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/3-540-60220-8_53","volume-title":"Algorithms and Data Structures","author":"C Phillips","year":"1995","unstructured":"Phillips, C., Stein, C., Wein, J.: Scheduling jobs that arrive over time. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol. 955, pp. 86\u201397. Springer, Heidelberg (1995)"},{"issue":"1","key":"24_CR13","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01581271","volume":"58","author":"M Queyranne","year":"1993","unstructured":"Queyranne, M.: Structure of a simple scheduling polyhedron. Math. Program. 58(1), 263\u2013285 (1993)","journal-title":"Math. Program."},{"key":"24_CR14","unstructured":"Queyranne, M., Schulz, A.S.: Polyhedral approaches to machine scheduling. Preprint 408\u20131994, TU Berlin (1994)"},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory B 80, 346\u2013355 (2000)","journal-title":"J. Comb. Theory B"},{"key":"24_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1007\/978-3-642-25591-5_55","volume-title":"Algorithms and Computation","author":"S Yasutake","year":"2011","unstructured":"Yasutake, S., Hatano, K., Kijima, S., Takimoto, E., Takeda, M.: Online linear optimization over permutations. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 534\u2013543. Springer, Heidelberg (2011)"},{"key":"24_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8431-1","volume-title":"Lectures on Polytopes. Graduate Texts in Mathematic","author":"GM Ziegler","year":"1995","unstructured":"Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematic, vol. 152. Springer, New York (1995)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09174-7_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T21:10:26Z","timestamp":1703193026000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-09174-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319091730","9783319091747"],"references-count":17,"aliases":["10.1007\/978-3-319-14115-2_24"],"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09174-7_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"22 July 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}