Strong conflict-free coloring for intervals Academic Article uri icon

abstract

  • We consider the \(k\)-strong conflict-free (\(k\)-SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval \(I\) of the family there are at least \(k\) colors each appearing exactly once in \(I\). We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when \(k=1\) and \(5-\frac{2}{k}\) when \(k\ge 2\). In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any \(k \ge 1\). We also provide, in case \(k=O({{\mathrm{polylog}}}(n))\), a quasipolynomial time algorithm to decide the existence of a \(k\)-SCF coloring that uses at most \(q\) colors.

publication date

  • January 1, 2014