{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T09:33:57Z","timestamp":1725701637255},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_15","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T11:29:11Z","timestamp":1346153351000},"page":"157-168","source":"Crossref","is-referenced-by-count":7,"title":["A Bicriteria Approximation for the Reordering Buffer Problem"],"prefix":"10.1007","author":[{"given":"Siddharth","family":"Barman","sequence":"first","affiliation":[]},{"given":"Shuchi","family":"Chawla","sequence":"additional","affiliation":[]},{"given":"Seeun","family":"Umboh","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Czumaj, A., Englert, M., R\u00e4cke, H.: Almost tight bounds for reordering buffer management. In: STOC (2011)","DOI":"10.1145\/1993636.1993717"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Asahiro, Y., Kawahara, K., Miyano, E.: Np-hardness of the sorting buffer problem on the uniform metric. Discrete Applied Mathematics (2012)","DOI":"10.1016\/j.dam.2012.02.005"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Avigdor-Elgrabli, N., Rabani, Y.: An improved competitive algorithm for reordering buffer management. In: SODA (2010)","DOI":"10.1137\/1.9781611973075.2"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Avigdor-Elgrabli, N., Rabani, Y.: A constant factor approximation algorithm for reordering buffer management. CoRR, abs\/1202.4504 (2012)","DOI":"10.1137\/1.9781611973105.70"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Pruhs, K.: Server scheduling in the l p norm: a rising tide lifts all boat. In: STOC 2003 (2003)","DOI":"10.1145\/780542.780580"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Barman, S., Chawla, S., Umboh, S.: A bicriteria approximation for the reordering buffer problem. CoRR, abs\/1204.5823 (2012)","DOI":"10.1007\/978-3-642-33090-2_15"},{"key":"15_CR7","unstructured":"Blandford, D., Blelloch, G.: Index compression through document reordering. In: Proceedings of the Data Compression Conference, DCC 2002 (2002)"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Chan, H.-L., Megow, N., Sitters, R., van Stee, R.: A note on sorting buffers offline. Theor. Comput. Sci. (2012)","DOI":"10.1016\/j.tcs.2011.12.077"},{"key":"15_CR9","unstructured":"Englert, M., R\u00e4cke, H., Westermann, M.: Reordering buffers for general metric spaces. Theory of Computing (2010)"},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/11523468_51","volume-title":"Automata, Languages and Programming","author":"M. Englert","year":"2005","unstructured":"Englert, M., Westermann, M.: Reordering Buffer Management for Non-uniform Cost Models. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 627\u2013638. Springer, Heidelberg (2005)"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci.\u00a069(3) (2004)","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Gamzu, I., Segev, D.: Improved online algorithms for the sorting buffer problem on line metrics. ACM Transactions on Algorithms (2009)","DOI":"10.1145\/1644015.1644030"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. Journal of the ACM\u00a047(4) (2000)","DOI":"10.1145\/347476.347479"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Khandekar, R., Pandit, V.: Online and offline algorithms for the sorting buffers problem on the line metric. Journal of Discrete Algorithms\u00a08(1) (2010)","DOI":"10.1016\/j.jda.2008.08.002"},{"key":"15_CR15","unstructured":"Krokowski, J., R\u00e4cke, H., Sohler, C., Westermann, M.: Reducing state changes with a pipeline buffer. In: VMV 2004 (2004)"},{"key":"15_CR16","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Handbook of scheduling: Algorithms, models, and performance analysis (2004)"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1007\/3-540-45749-6_71","volume-title":"Algorithms - ESA 2002","author":"H. R\u00e4cke","year":"2002","unstructured":"R\u00e4cke, H., Sohler, C., Westermann, M.: Online Scheduling for Sorting Buffers. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, p. 820. Springer, Heidelberg (2002)"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Tardos, \u00c9.: How bad is selfish routing? Journal of the ACM\u00a049(2) (2002)","DOI":"10.1145\/506147.506153"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028(2) (1985)","DOI":"10.1145\/2786.2793"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Spieckermann, S., Gutenschwager, K., Vosz, S.: A sequential ordering problem in automotive paint shops. International Journal of Production Research\u00a042(9) (2004)","DOI":"10.1080\/00207540310001646821"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:54:45Z","timestamp":1620114885000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}