Abstract
We consider the weighted Reordering Buffer Management problem. In this problem a set of n elements arrive over time one at a time and the elements can be stored in a buffer of size k. When the buffer becomes full, an element must be output. Elements are colored and if two elements are output consecutively and they have different colors then a switching cost is incurred. If the new color output is c, the cost is \(w_c\). The objective is to reorder the elements to minimize the total switching cost in the output sequence.
In this paper, we give an improved randomized \(O(\log \log \log k\gamma )\)-approximation for this problem where \(\gamma \) is the ratio of the maximum to minimum weight of a color, improving upon the previous best \(O(\log \log k\gamma )\)-approximation. Our improvement builds on strengthening the standard linear program for the problem with non-standard knapsack coveringinequalities. In particular, by leveraging the structure of these inequalities, our algorithm manages to render several random procedures more powerful and combine them effectively, thereby giving an exponential improvement upon the previous work.
S. Im—Supported in part by NSF grant CCF-1409130.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aboud, A.: Correlation clustering with penalties and approximating the reordering buffer management problem. Masters thesis, Computer Science Department, The Technion - Israel Institute of Technology (2008)
Adamaszek, A., Czumaj, A., Englert, M., Räcke, H.: Almost tight bounds for reordering buffer management. In: STOC, pp. 607–616 (2011)
Alborzi, H., Torng, E., Uthaisombut, P., Wagner, S.: The k-client problem. J. Algorithms 41(2), 115–173 (2001)
Asahiro, Y., Kawahara, K., Miyano, E.: Np-hardness of the sorting buffer problem on the uniform metric. Discrete Applied Mathematics 160(10–11), 1453–1464 (2012)
Avigdor-Elgrabli, N., Im, S., Moseley, B., Rabani, Y.: On the randomized competitive ratio of reordering buffer management with non-uniform costs. Manuscript (2014)
Avigdor-Elgrabli, N., Rabani, Y.: An improved competitive algorithm for reordering buffer management. In: SODA, pp. 13–21 (2010)
Avigdor-Elgrabli, N., Rabani, Y.: A constant factor approximation algorithm for reordering buffer management. In: SODA (2013)
Avigdor-Elgrabli, N., Rabani, Y.: An improved competitive algorithm for reordering buffer management. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, October 26–29, 2013, Berkeley, CA, USA, pp. 1–10 (2013)
Bar-Yehuda, R., Laserson, J.: Exploiting locality: approximating sorting buffers. J. Discrete Algorithms 5(4), 729–738 (2007)
Blandford, D.K., Blelloch, G.E.: Index compression through document reordering. In: DCC, pp. 342–351 (2002)
Carr, R.D., Fleischer, L.K., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, SODA 2000, Philadelphia, PA, USA, pp. 106–115. Society for Industrial and Applied Mathematics (2000)
Chan, H.-L., Megow, N., Sitters, R., van Stee, R.: A note on sorting buffers offline. Theor. Comput. Sci. 423, 11–18 (2012)
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. 3580, pp. 627–638. Springer, Heidelberg (2005)
Esfandiari, H., Hajiaghayi, M.T., Khani, M.R., Liaghat, V., Mahini, H., Räcke, H.: Online stochastic reordering buffer scheduling. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 465–476. Springer, Heidelberg (2014)
Gamzu, I., Segev, D.: Improved online algorithms for the sorting buffer problem on line metrics. ACM Transactions on Algorithms, 6(1) (2009)
Im, S., Moseley, B.: New approximations for reordering buffer management. In: SODA, pp. 1093–1111 (2014)
Khandekar, R., Pandit, V.: Online sorting buffers on line. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 584–595. Springer, Heidelberg (2006)
Kohrt, J.S., Pruhs, K.R.: A constant approximation algorithm for sorting buffers. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 193–202. Springer, Heidelberg (2004)
Krokowski, J., Räcke, H., Sohler, C., Westermann, M.: Reducing state changes with a pipeline buffer. In: VMV, pp. 217 (2004)
Räcke, H., Sohler, C., Westermann, M.: Online Scheduling for Sorting Buffers. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 820–832. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Im, S., Moseley, B. (2015). Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_60
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_60
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)