{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:46:50Z","timestamp":1725536810072},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_52","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"612-623","source":"Crossref","is-referenced-by-count":0,"title":["On the Structure of Optimal Greedy Computation (for Job Scheduling)"],"prefix":"10.1007","author":[{"given":"Periklis A.","family":"Papakonstantinou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"52_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-540-24592-6_3","volume-title":"Approximation and Online Algorithms","author":"S. Angelopoulos","year":"2004","unstructured":"Angelopoulos, S.: Randomized priority algorithms. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol.\u00a02909, pp. 27\u201340. Springer, Heidelberg (2004)"},{"key":"52_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/3-540-45753-4_5","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"S. Angelopoulos","year":"2002","unstructured":"Angelopoulos, S., Borodin, A.: On the power of priority algorithms for facility location and set cover. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 26\u201339. Springer, Heidelberg (2002)"},{"key":"52_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/11523468_76","volume-title":"Automata, Languages and Programming","author":"A. Borodin","year":"2005","unstructured":"Borodin, A., Cashman, D., Magen, A.: How well can primal-dual and local-ratio algorithms perform? In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 943\u2013955. Springer, Heidelberg (2005)"},{"issue":"4","key":"52_CR4","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00453-003-1036-3","volume":"37","author":"A. Borodin","year":"2003","unstructured":"Borodin, A., Nielsen, M.N., Rackoff, C. (Incremental) priority algorithms. Algorithmica (also SODA 2002)\u00a037(4), 295\u2013326 (2003)","journal-title":"Algorithmica (also SODA 2002)"},{"key":"52_CR5","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2000","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (2000)"},{"key":"52_CR6","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J. Edmonds","year":"1971","unstructured":"Edmonds, J.: Matroids and the greedy algorithm. Math. Programming\u00a01, 127\u2013136 (1971)","journal-title":"Math. Programming"},{"key":"52_CR7","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., 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"},{"issue":"2","key":"52_CR8","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/0406021","volume":"6","author":"P. Helman","year":"1993","unstructured":"Helman, P., Moret, B.M.E., Shapiro, H.D.: An exact characterization of greedy structures. SIAM J. Discrete Math.\u00a06(2), 274\u2013283 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"52_CR9","unstructured":"Horn, S.L.: One-pass algorithms with revocable acceptances for job interval selection. Master\u2019s thesis, University of Toronto (January 2004)"},{"key":"52_CR10","series-title":"Lecture Notes in Computer Science","first-page":"205","volume-title":"Programming Languages and their Definition","author":"B. Korte","year":"1984","unstructured":"Korte, B., Lovasz, L.: Mathematical structures underlying greedy algorithms. In: Bekic, H. (ed.) Programming Languages and their Definition. LNCS, vol.\u00a0177, pp. 205\u2013209. Springer, Heidelberg (1984)"},{"issue":"1-3","key":"52_CR11","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.tcs.2005.10.045","volume":"352","author":"P.A. Papakonstantinou","year":"2006","unstructured":"Papakonstantinou, P.A.: Hierarchies for priority algorithms for job scheduling. Theoretical Computer Science\u00a0352(1-3), 181\u2013189 (2006)","journal-title":"Theoretical Computer Science"},{"key":"52_CR12","unstructured":"Papakonstantinou, P.A., Rackoff, C.W.: Characterizing sets of jobs that admit optimal greedy-like algorithms. Journal of Scheduling (2007) (under review)"},{"issue":"3","key":"52_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0020-0190(02)00264-8","volume":"84","author":"O. Regev","year":"2003","unstructured":"Regev, O.: Priority algorithms for makespan minimization in the subset model. Information Processing Letters\u00a084(3), 153\u2013157 (2003)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T12:50:54Z","timestamp":1552135854000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}