{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:44:30Z","timestamp":1725795870760},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_39","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"465-476","source":"Crossref","is-referenced-by-count":5,"title":["Online Stochastic Reordering Buffer Scheduling"],"prefix":"10.1007","author":[{"given":"Hossein","family":"Esfandiari","sequence":"first","affiliation":[]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[]},{"given":"Mohammad Reza","family":"Khani","sequence":"additional","affiliation":[]},{"given":"Vahid","family":"Liaghat","sequence":"additional","affiliation":[]},{"given":"Hamid","family":"Mahini","sequence":"additional","affiliation":[]},{"given":"Harald","family":"R\u00e4cke","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","unstructured":"Aboud, A.: Correlation clustering with penalties and approximating the reordering buffer management problem. Master\u2019s thesis (2008)"},{"key":"39_CR2","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":"39_CR3","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Czumaj, A., Englert, M., R\u00e4cke, H.: Optimal online buffer scheduling for block devices. In: STOC (2012)","DOI":"10.1145\/2213977.2214031"},{"key":"39_CR4","unstructured":"Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming. CoRR (2009)"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Asahiro, Y., Kawahara, K., Miyano, E.: NP-hardness of the sorting buffer problem on the uniform metric. Discrete Appl. Math.\u00a0160(10-11) (2012)","DOI":"10.1016\/j.dam.2012.02.005"},{"key":"39_CR6","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":"39_CR7","doi-asserted-by":"crossref","unstructured":"Avigdor-Elgrabli, N., Rabani, Y.: A constant factor approximation algorithm for reordering buffer management. In: SODA (2013)","DOI":"10.1137\/1.9781611973105.70"},{"key":"39_CR8","doi-asserted-by":"crossref","unstructured":"Avigdor-Elgrabli, N., Rabani, Y.: An optimal randomized online algorithm for reordering buffer management. In: FOCS (2013)","DOI":"10.1137\/1.9781611973105.70"},{"key":"39_CR9","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: SODA (2007)"},{"key":"39_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-642-15775-2_15","volume-title":"Algorithms \u2013 ESA 2010","author":"B. Bahmani","year":"2010","unstructured":"Bahmani, B., Kapralov, M.: Improved Bounds for Online Stochastic Matching. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 170\u2013181. Springer, Heidelberg (2010)"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Naor, J(S.): A primal-dual randomized algorithm for weighted paging. In: FOCS (2007)","DOI":"10.1109\/FOCS.2007.43"},{"key":"39_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-642-15369-3_4","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Bateni","year":"2010","unstructured":"Bateni, M., Hajiaghayi, M., Zadimoghaddam, M.: Submodular secretary problem and extensions. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol.\u00a06302, pp. 39\u201352. Springer, Heidelberg (2010)"},{"key":"39_CR13","unstructured":"Blandford, D., Blelloch, G.: Index compression through document reordering. In: DCC (2002)"},{"issue":"2","key":"39_CR14","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/1998549.1998555","volume":"10","author":"Y. Cai","year":"2011","unstructured":"Cai, Y., Daskalakis, C., Weinberg, S.M.: On optimal multidimensional mechanism design. SIGecom Exch.\u00a010(2), 29\u201333 (2011)","journal-title":"SIGecom Exch."},{"key":"39_CR15","unstructured":"Chan, H.-L., Megow, N., van Stee, R., Sitters, R.: The sorting buffer problem is NP-hard. CoRR (2010)"},{"key":"39_CR16","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Sivan, B., Wilkens, C.A.: Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In: EC (2011)","DOI":"10.1145\/1993574.1993581"},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"Devenur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: EC (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"39_CR18","unstructured":"Dynkin, E.B.: The optimum choice of the instant for stopping a markov process. Soviet Math. Dokl\u00a04 (1963)"},{"key":"39_CR19","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":"39_CR20","doi-asserted-by":"crossref","unstructured":"Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: beating 1 \u2212 1\/e. In: FOCS (2009)","DOI":"10.1109\/FOCS.2009.72"},{"issue":"2","key":"39_CR21","doi-asserted-by":"publisher","first-page":"189","DOI":"10.2307\/1402748","volume":"51","author":"P.R. Freeman","year":"2011","unstructured":"Freeman, P.R.: The secretary problem and its extensions: a review. Inter. Statistical Review\u00a051(2), 189\u2013206 (2011)","journal-title":"Inter. Statistical Review"},{"key":"39_CR22","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: SODA (2008)"},{"key":"39_CR23","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Kleinberg, R.D., Leighton, T., R\u00e4cke, H.: New lower bounds for oblivious routing in undirected graphs. In: SODA (2006)","DOI":"10.1145\/1109557.1109658"},{"key":"39_CR24","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Kleinberg, R., Parkes, D.C.: Adaptive limited-supply online auctions. In: EC (2004)","DOI":"10.1145\/988772.988784"},{"key":"39_CR25","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Kim, J.H., Leighton, T., R\u00e4cke, H.: Oblivious routing in directed graphs with random demands. In: STOC (2005)","DOI":"10.1145\/1060590.1060619"},{"key":"39_CR26","doi-asserted-by":"crossref","unstructured":"Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: STOC (2011)","DOI":"10.1145\/1993636.1993715"},{"key":"39_CR27","unstructured":"Krokowski, J., R\u00e4cke, H., Sohler, C., Westermann, M.: Reducing state changes with a pipeline buffer. In: VMV (2004)"},{"key":"39_CR28","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In: STOC (2011)","DOI":"10.1145\/1993636.1993716"},{"key":"39_CR29","doi-asserted-by":"crossref","unstructured":"Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: online actions based on offline statistics. In: SODA (2011)","DOI":"10.1137\/1.9781611973082.98"},{"issue":"2","key":"39_CR30","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A. Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the chernoff\u2013hoeffding bounds. SIAM Journal on Computing\u00a026(2), 350\u2013368 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"39_CR31","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)"},{"issue":"9","key":"39_CR32","doi-asserted-by":"publisher","first-page":"1865","DOI":"10.1080\/00207540310001646821","volume":"42","author":"S. Spieckermann","year":"2004","unstructured":"Spieckermann, S., Gutenschwager, K., VoB\u0308, S.: A sequential ordering problem in automotive paint shops. International journal of production research\u00a042(9), 1865\u20131878 (2004)","journal-title":"International journal of production research"},{"issue":"3","key":"39_CR33","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/361268.361278","volume":"15","author":"T.J. Teorey","year":"1972","unstructured":"Teorey, T.J., PinkertonA, T.B.: comparative analysis of disk scheduling policies. Communications of the ACM\u00a015(3), 177\u2013184 (1972)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:26:48Z","timestamp":1558924008000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}