3
$\begingroup$

Consider the following optimization problem: given a finite set $S$ of intervals on the line and a number $k$. We need to colour this set in $k$ colours so that the measure of the set of points, which are contained in two or more intervals coloured with the same colour, is minimal for given $k$. By colouring a set $S$ in $k$ colours I mean a map from $S$ to $\{1,2,\ldots,k\}$.

Example: for three intervals $[0,3]$, $[1,4]$, $[2,5]$ and $k = 2$ we need to colour first and third interval in first colour and second interval in second colour, so the measure of the set of points, which are contained in two or more intervals coloured with the same colour, is $1$.

Motivation for this problem can be the following: we have $k$ guards and $S$ is a set of events to be observed. We need to partition these events into $k$ sets (one for every guard), minimizing the time when some guard observes more than one event.

I wonder if there are any papers on this problem or related problems.

Note: I have asked this question on mathoverflow, but didn't get a response. As this problem can be considered as scheduling optimization problem, I think it is closely related to computer science.

$\endgroup$
  • $\begingroup$ A clarification: do you want to minimize the sum of the lengths of the (sub)intervals having the same color? For example, for k=2 what is the "cost" of coloring [0,3], [1,4], [2,5], [3,5] with 1,2,1,2? Is it (3-2)+(4-3) = 2? $\endgroup$ – Marzio De Biasi Jan 29 '14 at 13:04
  • $\begingroup$ @MarzioDeBiasi, I am interested in references about all formulations, similar to the described one, but in my formulation the amount of time, which is "unsafe" (i.e. when at least one guard is observing more than one event) is minimized. $\endgroup$ – Andrew Ryzhikov Jan 29 '14 at 13:06
  • $\begingroup$ @MarzioDeBiasi, and yes, for your example the cost will be $2$, but it will be $1$ for $[0,3]$, $[1,3]$, $[2,5]$, $[2,5]$ coloured 1, 2, 1, 2. $\endgroup$ – Andrew Ryzhikov Jan 29 '14 at 13:10
  • $\begingroup$ Are you sure? In you example $[0,3],[2,5]$ are colored with $1$ so the overlap time is $1$; $[1,3],[2,5]$ are colored with $2$ and the overlap time is $1$; so the total overlap time is still $2$ $\endgroup$ – Marzio De Biasi Jan 29 '14 at 13:29
  • 2
    $\begingroup$ In general, we do not allow simultaneous cross-posting to MO and cstheory because it splinters conversations. Please try to avoid this in the future. $\endgroup$ – Artem Kaznatcheev Jan 29 '14 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.