Variable Sized Online Interval Coloring with Bandwidth
Tóm tắt
We consider online coloring of intervals with bandwidth in a setting where colors have variable capacities. Whenever the algorithm opens a new color, it must choose the capacity for that color and cannot change it later. A set of intervals can be assigned the same color a of capacity C
a
if the sum of bandwidths of intervals at each point does not exceed C
a
. The goal is to minimize the total capacity of all the colors used. We consider the bounded model, where all capacities must be chosen in the range (0,1], and the unbounded model, where the algorithm may use colors of any positive capacity. For the absolute competitive ratio, we give an upper bound of 14 and a lower bound of 4.59 for the bounded model, and an upper bound of 4 and a matching lower bound of 4 for the unbounded model. We also consider the offline version of these problems and show that whereas the unbounded model is polynomially solvable, the bounded model is NP-hard in the strong sense and admits a 3.6-approximation algorithm.
Tài liệu tham khảo
Adamy, U., Erlebach, T.: Online coloring of intervals with bandwidth. In: Proceedings of the First International Workshop on Approximation and Online Algorithms (WAOA’03). Lecture Notes in Computer Science, vol. 2909, pp. 1–12 (2003)
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S.A., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3), 486–504 (1997)
Azar, Y., Fiat, A., Levy, M., Narayanaswamy, N.: An improved algorithm for online coloring of intervals with bandwidth. Theor. Comput. Sci. 363(1), 18–27 (2006)
Baruah, S.K., Koren, G., Mao, D., Mishra, B., Raghunathan, A., Rosier, L.E., Shasha, D., Wang, F.: On the competitiveness of on-line real-time task scheduling. Real-Time Syst. 4(2), 125–144 (1992)
Chrobak, M., Ślusarek, M.: On some packing problems relating to dynamical storage allocation. RAIRO J. Inf. Theory Appl. 22, 487–499 (1988)
Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms. PWS (1997)
Csirik, J.: An online algorithm for variable-sized bin packing. Acta Inf. 26, 697–709 (1989)
Csirik, J., Woeginger, G.J.: On-line packing and covering problems. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms: The State of the Art. Lecture Notes in Computes Science, vol. 1442, pp. 147–177 (1998)
de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within 1+ε in linear time. Combinatorica 1, 349–355 (1981)
Epstein, L., Levy, M.: Online interval coloring and variants. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP’05). Lecture Notes in Computer Science, vol. 3580, pp. 602–613 (2005)
Epstein, L., Levy, M.: Online interval coloring with packing constraints. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS’05). Lecture Notes in Computer Science, vol. 3618, pp. 295–307 (2005)
Friesen, D.K., Langston, M.A.: Variable sized bin packing. SIAM J. Comput. 15, 222–230 (1986)
Garey, M.R., Johnson, D.S.: Computer and Intractability. W.H. Freeman, New York (1979)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic, New York (1980)
Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley, New York (1995)
Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS’82), pp. 312–320 (1982)
Kierstead, H.A.: The linearity of first-fit coloring of interval graphs. SIAM J. Discrete Math. 1(4), 526–530 (1988)
Kierstead, H.A., Qin, J.: Coloring interval graphs with First-Fit. SIAM J. Discrete Math. 8, 47–57 (1995)
Kierstead, H.A., Trotter, W.T.: An extremal problem in recursive combinatorics. Congr. Numer. 33, 143–153 (1981)
Lee, C.C., Lee, D.T.: A simple online bin packing algorithm. J. ACM 32(3), 562–572 (1985)
Murgolo, F.D.: An efficient approximation scheme for variable-sized bin packing. SIAM J. Comput. 16(1), 149–161 (1987)
Narayanaswamy, N.S.: Dynamic storage allocation and online colouring interval graphs. In: Proceedings of the 10th Annual International Conference on Computing and Combinatorics (COCOON’04). Lecture Notes in Computer Science, vol. 3106, pp. 329–338 (2004)
Pemmaraju, S.V., Raman, R., Varadarajan, K.R.: Buffer minimization using max-coloring. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’04), pp. 562–571 (2004)
Seiden, S.S.: An optimal online algorithm for bounded space variable-sized bin packing. SIAM J. Discrete Math. 14(4), 458–470 (2001)
Seiden, S.S.: On the online bin packing problem. J. ACM 49(5), 640–671 (2002)
Seiden, S.S., van Stee, R., Epstein, L.: New bounds for variable-sized online bin packing. SIAM J. Comput. 32(2), 455–469 (2003)
Ullman, J.D.: The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ (1971)