{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T02:25:27Z","timestamp":1648952727560},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,12,17]],"date-time":"2009-12-17T00:00:00Z","timestamp":1261008000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s10951-009-0148-2","type":"journal-article","created":{"date-parts":[[2009,12,16]],"date-time":"2009-12-16T14:25:19Z","timestamp":1260973519000},"page":"163-176","source":"Crossref","is-referenced-by-count":0,"title":["Characterizing sets of jobs that admit optimal greedy-like algorithms"],"prefix":"10.1007","volume":"13","author":[{"given":"Periklis A.","family":"Papakonstantinou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles W.","family":"Rackoff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,12,17]]},"reference":[{"key":"148_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Borodin, A., Buresh-Oppenheim, J., Impagliazzo, R., Magen, A., & Pitassi, T. (2005). Towards a model for backtracking and dynamic programming. In Proceedings of the 20th annual IEEE conference on computational complexity (CCC) (pp.\u00a0308\u2013322).","DOI":"10.1109\/CCC.2005.32"},{"key":"148_CR2","series-title":"Lecture notes in computer science","first-page":"27","volume-title":"Approximation and online algorithms, Proceedings of the 1st international workshop, WAOA","author":"S. Angelopoulos","year":"2003","unstructured":"Angelopoulos, S. (2003). Randomized priority algorithms. In Lecture notes in computer science : Vol. 2909. Approximation and online algorithms, Proceedings of the 1st international workshop, WAOA (pp. 27\u201340). Berlin: Springer."},{"key":"148_CR3","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/3-540-45753-4_5","volume-title":"Approximation algorithms for combinatorial optimization, Proceedings of the 5th international workshop, APPROX","author":"S. Angelopoulos","year":"2002","unstructured":"Angelopoulos, S., & Borodin, A. (2002). On the power of priority algorithms for facility location and set cover. In Lecture notes in computer science : Vol. 2462. Approximation algorithms for combinatorial optimization, Proceedings of the 5th international workshop, APPROX (pp. 26\u201339). Berlin: Springer."},{"key":"148_CR4","doi-asserted-by":"crossref","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. L. (1987). Scheduling jobs with fixed start and end times. Discrete and Applied Mathematics, 18, 1\u20138.","journal-title":"Discrete and Applied Mathematics"},{"key":"148_CR5","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1007\/11523468_76","volume-title":"Proceedings of the automata, languages and programming (ICALP)","author":"A. Borodin","year":"2005","unstructured":"Borodin, A., Cashman, D., & Magen, A. (2005). How well can primal-dual and local-ratio algorithms perform? In Lecture notes in computer science : Vol. 3580. Proceedings of the automata, languages and programming (ICALP) (pp. 943\u2013955). Berlin: Springer."},{"issue":"4","key":"148_CR6","doi-asserted-by":"crossref","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. (2003). (Incremental) Priority algorithms. Algorithmica, 37(4), 295\u2013326.","journal-title":"Algorithmica"},{"issue":"3","key":"148_CR7","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0166-218X(95)80003-M","volume":"59","author":"M. C. Carlisle","year":"1995","unstructured":"Carlisle, M. C., & Lloyd, E. L. (1995). On the k-coloring of intervals. Discrete Applied Mathematics, 59(3), 225\u2013235.","journal-title":"Discrete Applied Mathematics"},{"key":"148_CR8","volume-title":"Introduction to algorithms","author":"T. H. Cormen","year":"2002","unstructured":"Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2002). Introduction to algorithms. Cambridge: MIT Press."},{"key":"148_CR9","first-page":"381","volume-title":"Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms, SODA","author":"S. Davis","year":"2004","unstructured":"Davis, S., & Impagliazzo, R. (2004). Models of greedy algorithms for graph problems. In Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 381\u2013390). Philadelphia: SIAM."},{"key":"148_CR10","doi-asserted-by":"crossref","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.\u00a0H.\u00a0G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"key":"148_CR11","unstructured":"Horn, S. L. (2004). One-pass algorithms with revocable acceptances for job interval selection. MSc Thesis, University of Toronto."},{"key":"148_CR12","volume-title":"Computational complexity","author":"C. H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C. H. (1994). Computational complexity. Reading-Harlow: Addison-Wesley\u2013Longman."},{"issue":"1\u20133","key":"148_CR13","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.tcs.2005.10.045","volume":"352","author":"P. A. Papakonstantinou","year":"2006","unstructured":"Papakonstantinou, P. A. (2006). Hierarchies for priority algorithms for job scheduling. Theoretical Computer Science, 352(1\u20133), 181\u2013189.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"148_CR14","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0020-0190(02)00264-8","volume":"84","author":"O. Regev","year":"2003","unstructured":"Regev, O. (2003). Priority algorithms for makespan minimization in the subset model. Information Processing Letters, 84(3), 153\u2013157.","journal-title":"Information Processing Letters"},{"key":"148_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to circuit complexity\u2014a uniform approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H. (1999). Introduction to circuit complexity\u2014a uniform approach. Berlin: Springer."}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-009-0148-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-009-0148-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-009-0148-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T05:39:43Z","timestamp":1559453983000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-009-0148-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,17]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["148"],"URL":"https:\/\/doi.org\/10.1007\/s10951-009-0148-2","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,17]]}}}