Abstract
In the buffer minimization in multiprocessor systems with conflicts or simply buffer minimization problem, a multi-processor system is modelled as an undirected graph. A conflict occurs if two processors are connected by an edge. Conflicting processors can not run at the same time. At any time, load may arrive on one or more processors. Incoming workload is stored in an input buffer and a machine that is running reduces its workload at a constant rate. The goal is to find a schedule that minimizes the maximum workload over all machines. We consider the special case where the graph is a path and give bounds on the competitive ratio for small graph sizes, including a tight bound of 9/4 for a path with 4 nodes. We give a general lower bound of 12/5. We also consider online algorithms that have resource augmentation on their speed, and give a \((1+\varepsilon )\)-speed \((1/\varepsilon +3)\)-competitive algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bodlaender, M.H.L., Hurkens, C.A.J., Kusters, V.J.J., Staals, F., Woeginger, G.J., Zantema, H.: Cinderella versus the wicked stepmother. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds.) TCS 2012. LNCS, vol. 7604, pp. 57–71. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33475-7_5
Chrobak, M., Csirik, J., Imreh, C., Noga, J., Sgall, J., Woeginger, G.J.: The buffer minimization problem for multiprocessor scheduling with conflicts. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 862–874. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-48224-5_70
Gąsieniec, L., Klasing, R., Levcopoulos, C., Lingas, A., Min, J., Radzik, T.: Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors). In: Steffen, B., Baier, C., van den Brand, M., Eder, J., Hinchey, M., Margaria, T. (eds.) SOFSEM 2017. LNCS, vol. 10139, pp. 229–240. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-51963-0_18
Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416–429 (1969)
Irani, S., Leung, V.J.: Scheduling with conflicts, and applications to traffic signal control. In: Tardos, É. (ed.) Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, Georgia, USA, 28–30 January 1996, pp. 85–94. ACM/SIAM (1996)
Irani, S., Leung, V.J.: Probabilistic analysis for scheduling with conflicts. In: Saks, M.E. (ed.) Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, 5–7 January 1997, pp. 286–295. ACM/SIAM (1997)
Sgall, J.: Open problems in throughput scheduling. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 2–11. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33090-2_2
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Höhne, F., van Stee, R. (2020). Buffer Minimization with Conflicts on a Line. In: Li, M. (eds) Frontiers in Algorithmics. FAW 2020. Lecture Notes in Computer Science(), vol 12340. Springer, Cham. https://doi.org/10.1007/978-3-030-59901-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-59901-0_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-59900-3
Online ISBN: 978-3-030-59901-0
eBook Packages: Computer ScienceComputer Science (R0)