{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:00Z","timestamp":1750307820530,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n            The seat reservation problem is the problem of assigning passengers to seats on a train with\n            <jats:italic>n<\/jats:italic>\n            seats and\n            <jats:italic>k<\/jats:italic>\n            stations enroute in an online manner. The performance of algorithms for this problem is studied using the relative worst order ratio, a fairly new measure for the quality of online algorithms, which allows for direct comparisons between algorithms. This study has yielded new separations between algorithms. For example, for both variants of the problem considered, using the relative worst order ratio, First-Fit and Best-Fit are shown to be better than Worst-Fit.\n          <\/jats:p>","DOI":"10.1145\/1383369.1383379","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T11:56:36Z","timestamp":1219838196000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["The relative worst order ratio applied to seat reservation"],"prefix":"10.1145","volume":"4","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[{"name":"University of Southern Denmark, Odense M, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022985808959"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294264"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240245"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-003-0124-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009286"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361786"},{"key":"e_1_2_1_8_1","unstructured":"Boyar J. and Medvedev P. 2007. The relative worst order ratio applied to seat reservation. Tech. rep. PP--2007--03 Department of Mathematics and Computer Science University of Southern Denmark.  Boyar J. and Medvedev P. 2007. The relative worst order ratio applied to seat reservation. Tech. rep. PP--2007--03 Department of Mathematics and Computer Science University of Southern Denmark."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1988220404871"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"A survey of performance measures for online algorithms","volume":"36","author":"Dorrigiv R.","year":"2005","journal-title":"SIGACT News"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-9005-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_13_1","unstructured":"Graham R. L. Knuth D. E. and Patashnik O. 1988. Concrete Mathematics. Equation 5.23. Addison-Wesley.   Graham R. L. Knuth D. E. and Patashnik O. 1988. Concrete Mathematics. Equation 5.23. Addison-Wesley."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80026-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 359--364","year":"1996","author":"Kenyon C.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","first-page":"143","article-title":"An extremal problem in recursive combinatorics","volume":"33","author":"Kierstead H. A.","year":"1981","journal-title":"Congressus Numerantium"},{"key":"e_1_2_1_18_1","unstructured":"Kohrt J. S. 2004. Online algorithms under new assumptions. Ph.D. thesis Department of Mathematics and Computer Science University of Southern Denmark Odense Denmark.  Kohrt J. S. 2004. Online algorithms under new assumptions. Ph.D. thesis Department of Mathematics and Computer Science University of Southern Denmark Odense Denmark."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383379","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1383369.1383379","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:46Z","timestamp":1750255066000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383379"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1383369.1383379"],"URL":"https:\/\/doi.org\/10.1145\/1383369.1383379","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2006-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}