Deterministic conflict-free coloring for intervals: From offline to online

ABSTRACT

We investigate deterministic algorithms for a frequency assignment problem in cellular networks. The problem can be modeled as a special vertex coloring problem for hypergraphs: In every hyperedge there must exist a vertex with a color that occurs exactly once in the hyperedge (the conflict-free property). We concentrate on a special case of the problem, called conflict-free coloring for intervals. We introduce a hierarchy of four models for the aforesaid problem: (i) static, (ii) dynamic offline, (iii) dynamic online with absolute positions, and (iv) dynamic online with relative positions. In the dynamic offline model, we give a deterministic algorithm that uses at most log_3/2 n + 1 &;approx; 1.71 log₂ n colors and show inputs that force any algorithm to use at least 3 log₅ n + 1 ≈ 1.29 log₂ n colors. For the online absolute-positions model, we give a deterministic algorithm that uses at most 3⌈log₃ n⌉ ≈ 1.89 log₂ n colors. To the best of our knowledge, this is the first deterministic online algorithm using O(log n) colors in a nontrivial online model. In the online relative-positions model, we resolve an open problem by showing a tight analysis on the number of colors used by the first-fit greedy online algorithm. We also consider conflict-free coloring only with respect to intervals that contain at least one of the two extreme points.

REFERENCES

• 1: Deepak Ajwani , Khaled Elbassioni , Sathish Govindarajan , Saurabh Ray, Conflict-free coloring for rectangle ranges using O(n^.382) colors, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248406]
• 2: Noga Alon , Shakhar Smorodinsky, Conflict-free colorings of shallow discs, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137864]
• 3: Bar-Noy, A., Cheilaris, P., Olonetsky, S., and Smorodinsky, S. 2007. Online conflict-free coloring for geometric hypergraphs. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), 219--230.
• 4: Amotz Bar-Noy , Panagiotis Cheilaris , Shakhar Smorodinsky, Conflict-free coloring for intervals: from offline to online, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148133]
• 5: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 6: Ke Chen, How to play a coloring game against a color-blind adversary, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137865]
• 7: Ke Chen , Amos Fiat , Haim Kaplan , Meital Levy , Jirˇi´ Matousˇek , Elchanan Mossel , Ja´nos Pach , Micha Sharir , Shakhar Smorodinsky , Uli Wagner , Emo Welzl, Online Conflict-Free Coloring for Intervals, SIAM Journal on Computing, v.36 n.5, p.1342-1359, December 2006 [doi>10.1137/S0097539704446682]
• 8: Chen, K., Kaplan, H., and Sharir, M. 2006. Online conflict free coloring for halfplanes, congruent disks, and axis-parallel rectangles. Manuscript.
• 9: Elbassioni, K. , and Mustafa, N. H. 2006. Conflict-Free colorings of rectangles ranges. In Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), 254--263.
• 10: Guy Even , Zvi Lotker , Dana Ron , Shakhar Smorodinsky, Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks, SIAM Journal on Computing, v.33 n.1, p.94-136, 2004 [doi>10.1137/S0097539702431840]
• 11: Amos Fiat , Meital Levy , Jiří Matoušek , Elchanan Mossel , János Pach , Micha Sharir , Shakhar Smorodinsky , Uli Wagner , Emo Welzl, Online conflict-free coloring for intervals, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 12: Sariel Har-Peled , Shakhar Smorodinsky, Conflict-Free Coloring of Points and Simple Regions in the Plane, Discrete & Computational Geometry, v.34 n.1, p.47-70, July 2005 [doi>10.1007/s00454-005-1162-6]
• 13: Ananth, V. Iyer , H. Donald Ratliff , G. Vijayan, Optimal node ranking of trees, Information Processing Letters, v.28 n.5, p.225-229, Aug. 12, 1988 [doi>10.1016/0020-0190(88)90194-9]
• 14: Meir Katchalski , William McCuaig , Suzanne Seager, Ordered colourings, Discrete Mathematics, v.142 n.1-3, p.141-154, July 15, 1995 [doi>10.1016/0012-365X(93)E0216-Q]
• 15: Katz, M. J., Lev-Tov, N., and Morgenstern, G. 2007. Conflict-Free coloring of points on a line with respect to a set of intervals. In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG), 93--96.
• 16: Pach, J. , and Tóth, G. 2003. Conflict free colorings. In Discrete and Computational Geometry, The Goodman-Pollack Festschrift. Springer, 665--671.
• 17: Smorodinsky, S. 2003. Combinatorial problems in computational geometry. Ph.D. thesis, School of Computer Science, Tel-Aviv University.
• 18: Shakhar Smorodinsky, On The Chromatic Number of Geometric Hypergraphs, SIAM Journal on Discrete Mathematics, v.21 n.3, p.676-687, July 2007 [doi>10.1137/050642368]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
Online algorithms, cellular networks, coloring, conflict free, frequency assignment