{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:27:24Z","timestamp":1725560844575},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540210795"},{"type":"electronic","value":"9783540245926"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24592-6_3","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T03:13:33Z","timestamp":1280373213000},"page":"27-40","source":"Crossref","is-referenced-by-count":4,"title":["Randomized Priority Algorithms"],"prefix":"10.1007","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Albers, S.: On randomized online scheduling. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computation, pp. 134\u2013143 (2002)","DOI":"10.1145\/509907.509930"},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/3-540-45753-4_5","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"Spyros Angelopoulos","year":"2002","unstructured":"Angelopoulos, S., Borodin, A.: On the power of priority algorithms for facility location and set cover. In: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 26\u201339 (2002)"},{"issue":"2","key":"3_CR3","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A. Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Approximating throughput in real-time scheduling. SIAM Journal of Computing\u00a031(2), 331\u2013352 (2001)","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"3_CR4","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/jcss.1995.1074","volume":"51","author":"Y. Bartal","year":"1995","unstructured":"Bartal, Y., Fiat, A., Karloff, H., Vohra, R.: New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences\u00a051(3), 359\u2013366 (1995)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"3_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01294260","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A., Karp, R., Tardos, G., Wigderson, A.: On the power of randomization in online algorithms. Algorithmica\u00a011(1), 2\u201314 (1994)","journal-title":"Algorithmica"},{"key":"3_CR6","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"4","key":"3_CR7","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A. Borodin","year":"1992","unstructured":"Borodin, A., Linial, N., Saks, M.E.: An optimal algorithm for metrical task systems. Journal of the ACM\u00a039(4), 745\u2013763 (1992)","journal-title":"Journal of the ACM"},{"key":"3_CR8","unstructured":"Borodin, A., Nielsen, M., Rackoff, C.: (Incremental) priority algorithms. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 752\u2013761 (2002)"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(94)00110-3","volume":"51","author":"B. Chen","year":"1994","unstructured":"Chen, B., van Vliet, A., Woeginger, G.J.: A lower bound for randomized on-line scheduling algorithms. Information Processing Letters\u00a051, 219\u2013222 (1994)","journal-title":"Information Processing Letters"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0020-0190(97)00099-9","volume":"63","author":"M. Chrobak","year":"1997","unstructured":"Chrobak, M., Larmore, L., Reingold, N., Westbrook, J.: A better lower bound on the competitive ratio of the randomized 2-server problem. Information Processing Letters\u00a063, 79\u201383 (1997)","journal-title":"Information Processing Letters"},{"key":"3_CR11","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1007\/3-540-45253-2_19","volume-title":"Algorithms - ESA 2000","author":"Rudolf Fleischer","year":"2000","unstructured":"Fleischer, R., Wahl, M.: Online scheduling revisited. In: Proceedings of the 8th Annual European Symposium on Algorithms, pp. 202\u2013210 (2000)"},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/3-540-45061-0_51","volume-title":"Automata, Languages and Programming","author":"Dimitris Fotakis","year":"2003","unstructured":"Fotakis, D.: On the competitive ratio for online facility location. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming, pp. 637\u2013652 (2003)"},{"key":"3_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, 2nd edn. Freeman, New York (1983)","edition":"2"},{"key":"3_CR14","unstructured":"Gormley, T., Reingold, N., Torng, E., Westbrook, J.: Generating adversaries for request-answer games. In: Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 564\u2013565 (2000)"},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Sys. Tech. J.\u00a045, 1563\u20131581 (1966)","journal-title":"Bell Sys. Tech. J."},{"issue":"2","key":"3_CR16","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R.L. Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics\u00a017(2), 416\u2013429 (1969)","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"3_CR17","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. In: Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 649\u2013657 (1998)"},{"issue":"1","key":"3_CR18","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of the ACM\u00a034(1), 144\u2013162 (1987)","journal-title":"Journal of the ACM"},{"key":"3_CR19","unstructured":"Impagliazzo, R., Davis, S.: Models of greedy algorithms for graph problems. In: Proceedings of the 15th Symposium on Discrete Algorithms (2004) (to appear)"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computation, pp. 731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"key":"3_CR21","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/3-540-44666-4_16","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"Mohammad Mahdian","year":"2001","unstructured":"Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: A greedy facility location algorithm analyzed using dual fitting. In: Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 127\u2013137 (2001)"},{"key":"3_CR22","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"Mohammad Mahdian","year":"2002","unstructured":"Mahdian, M., Ye, J., Zhang, J.: A 1.52-approximation algorithm for the uncapacitated facility location problem. In: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 229\u2013242 (2002)"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Mettu, R.R., Plaxton, C.G.: The online median problem. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pp. 339\u2013348 (2000)","DOI":"10.1109\/SFCS.2000.892122"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 426\u2013431 (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"issue":"1","key":"3_CR25","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S.K. Sahni","year":"1976","unstructured":"Sahni, S.K.: Algorithms for scheduling independent tasks. Journal of the ACM\u00a023(1), 116\u2013127 (1976)","journal-title":"Journal of the ACM"},{"issue":"5","key":"3_CR26","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0167-6377(00)00053-5","volume":"27","author":"S. Seiden","year":"2000","unstructured":"Seiden, S., Sgall, J., Woeginger, G.J.: Semi-online scheduling with decreasing job sizes. Operations Research Letters\u00a027(5), 215\u2013221 (2000)","journal-title":"Operations Research Letters"},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0020-0190(97)00093-8","volume":"63","author":"J. Sgall","year":"1997","unstructured":"Sgall, J.: A lower bound for randomized on-line multiprocessor scheduling. Information Processing Letters\u00a063, 51\u201355 (1997)","journal-title":"Information Processing Letters"},{"key":"3_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/BFb0029570","volume-title":"Online Algorithms","author":"J. Sgall","year":"1998","unstructured":"Sgall, J.: On-line scheduling\u2013a survey. In: Fiat, A., Woeginger, G. (eds.) Online Algorithms. LNCS, vol.\u00a01442, pp. 196\u2013231. Springer, Heidelberg (1998)"},{"key":"3_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/3-540-44436-X_4","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"D.B. Shmoys","year":"2000","unstructured":"Shmoys, D.B.: Approximation algorithms for facility location problems. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol.\u00a01913, pp. 27\u201332. Springer, Heidelberg (2000)"},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24592-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T19:38:12Z","timestamp":1559331492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24592-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540210795","9783540245926"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24592-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}