{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:57:03Z","timestamp":1725559023594},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_9","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T13:27:29Z","timestamp":1279027649000},"page":"90-101","source":"Crossref","is-referenced-by-count":9,"title":["The Relative Worst Order Ratio Applied to Seat Reservation"],"prefix":"10.1007","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/3-540-61680-2_73","volume-title":"Algorithms - ESA \u201996","author":"B. Awerbuch","year":"1996","unstructured":"Awerbuch, B., Azar, Y., Fiat, A., Leonardi, S., Ros\u00e9n, A.: On-line competitive algorithms for call admission in optical networks. In: D\u00edaz, J. (ed.) ESA 1996. LNCS, vol.\u00a01136, pp. 431\u2013444. Springer, Heidelberg (1996)"},{"key":"9_CR2","unstructured":"Awerbuch, B., Bartal, Y., Fiat, A., Ros\u00e9n, A.: Competitive non-preemptive call control. In: 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 312\u2013320 (1994)"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1023\/A:1022985808959","volume":"6","author":"E. Bach","year":"2003","unstructured":"Bach, E., Boyar, J., Epstein, L., Favrholdt, L.M., Jiang, T., Larsen, K.S., Lin, G.-H., van Stee, R.: Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem. J. Sched.\u00a06, 131\u2013147 (2003)","journal-title":"J. Sched."},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Bar-Noy, R., Canetti, S., Kutten, Y., Mansour, Y., Schieber, B.: Bandwidth allocation with preemption. In: 27th Annual ACM Symposium on the Theory of Computing, pp. 616\u2013625 (1995)","DOI":"10.1145\/225058.225279"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A.: A new measure for the study of on-line algorithms. Algorithmica\u00a011(1), 73\u201391 (1994)","journal-title":"Algorithmica"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/3-540-44849-7_13","volume-title":"Algorithms and Complexity","author":"J. Boyar","year":"2003","unstructured":"Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol.\u00a02653, pp. 58\u201369. Springer, Heidelberg (2003)"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M.: The relativeworst order ratio for on-line bin packing algorithms. Tech. report PP\u20132003\u201313, Department of Mathematics and Computer Science, University of Southern Denmark, Main Campus: Odense University (2003)","DOI":"10.1007\/3-540-44849-7_13"},{"key":"9_CR8","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst order ratio applied to paging. Tech. report ALCOMFT-TR-03-32, Future and Emerging Technologies program under the EU, contract number IST-1999-14186 (2003)"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00236-003-0124-9","volume":"40","author":"J. Boyar","year":"2003","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S., Nielsen, M.N.: Extending the accommodating function. Acta Informatica\u00a040, 3\u201335 (2003)","journal-title":"Acta Informatica"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/PL00009286","volume":"25","author":"J. Boyar","year":"1999","unstructured":"Boyar, J., Larsen, K.S.: The seat reservation problem. Algorithmica\u00a025, 403\u2013417 (1999)","journal-title":"Algorithmica"},{"issue":"1","key":"9_CR11","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1137\/S0097539799361786","volume":"31","author":"J. Boyar","year":"2001","unstructured":"Boyar, J., Larsen, K.S., Nielsen, M.N.: The accommodating function:A generalization of the competitive ratio. SIAM J. Comput.\u00a031(1), 233\u2013258 (2001)","journal-title":"SIAM J. Comput."},{"key":"9_CR12","unstructured":"Epstein, L., Favrholdt, L.M., Kohrt, J.S.: The relativeworst order ratio applied to scheduling problems. Work in progress (2004)"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jagm.1996.0821","volume":"23","author":"J.A. Garay","year":"1997","unstructured":"Garay, J.A., Gopal, I.S., Kutten, S., Mansour, Y., Yung, M.: Efficient on-line call control algorithms. J. Algorithms\u00a023, 180\u2013194 (1997)","journal-title":"J. Algorithms"},{"key":"9_CR14","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 Systems Technical Journal\u00a045, 1563\u20131581 (1966)","journal-title":"Bell Systems Technical Journal"},{"key":"9_CR15","volume-title":"Graph Coloring Problems","author":"T.R. Jensen","year":"1995","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. JohnWiley & Sons, West Sussex (1995)"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Fast algorithms for bin packing. Journal of Computer and System Sciences\u00a08, 272\u2013314 (1974)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"R. Karlin","year":"1988","unstructured":"Karlin, R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica\u00a03(1), 79\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"9_CR18","unstructured":"Kenyon, C.: Best-Fit bin-packing with random order. In: 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 359\u2013364 (1996)"},{"key":"9_CR19","first-page":"143","volume":"33","author":"H.A. Kierstead","year":"1981","unstructured":"Kierstead, H.A., Trotter, W.T.: An extremal problem in recursive combinatorics. Congr. Numer.\u00a033, 143\u2013153 (1981)","journal-title":"Congr. Numer."},{"key":"9_CR20","unstructured":"Kohrt, J.S.: The relative worst order ratio applied to bin coloring. Work in progress (2004)"},{"key":"9_CR21","unstructured":"Lipton, R.J.,Tomkins, A .: Online interval scheduling. In: 5th AnnualACM-SIAMSymposium on Discrete Algorithms, pp. 302\u2013311 (1994)"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Raghavan, P., Upfal, E.: Efficient routing in all-optical networks. In: 26th Annual ACM Symposium on the Theory of Computing, pp. 134\u2013143 (1994)","DOI":"10.1145\/195058.195119"},{"issue":"2","key":"9_CR23","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Comm. of the ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Comm. of the ACM"},{"issue":"2","key":"9_CR24","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M. Yannakakis","year":"1987","unstructured":"Yannakakis, M., Gavril, F.: The maximum k-colorable subgraph problem for chordal graphs. Information Processing Letters\u00a024(2), 133\u2013137 (1987)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:21:47Z","timestamp":1605741707000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}