<p>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\}$.</p>

<p>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$.</p>

<p>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.</p>

<p>I wonder if there are any papers on this problem or related problems.</p>

<p>Note: I have asked <a href="https://mathoverflow.net/questions/155920/minimize-the-length-of-intersection-of-the-set-of-intervals">this question on mathoverflow</a>, 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.</p>

CC BY-SA 3.0
2014-01-29T13:04:14.197Z
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?
Marzio De Biasi
CC BY-SA 3.0
2014-01-29T13:06:02.103Z
@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.
Andrew Ryzhikov
CC BY-SA 3.0
2014-01-29T13:10:03.997Z
@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.
Andrew Ryzhikov
CC BY-SA 3.0
2014-01-29T13:29:35.603Z
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$
Marzio De Biasi
CC BY-SA 3.0
2014-01-29T13:37:34.480Z
@MarzioDeBiasi, in my formulation the total measure of time when at least one guard is observing more than one event is counted. This time is $[2, 3]$, so the cost is $1$. This is quite unintuitive, but it is exactly what I describe in the question.
Andrew Ryzhikov
CC BY-SA 3.0
2014-01-29T13:49:54.410Z
Ok! Now it's clear
Marzio De Biasi
CC BY-SA 3.0
2014-01-29T14:39:09.880Z
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.
Artem Kaznatcheev
<reference-request><optimization><scheduling>
Minimize the time when guard observes more than one event (for fixed number of guards)
Andrew Ryzhikov
# Minimize the time when guard observes more than one event (for fixed number of guards)

(Asked by: username_0 on 2014-01-29)

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](https://mathoverflow.net/questions/155920/minimize-the-length-of-intersection-of-the-set-of-intervals), 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.

**Tags:** reference-request, optimization, scheduling

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_0**: @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.  
> **username_1**: 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$  
> **username_0**: @MarzioDeBiasi, in my formulation the total measure of time when at least one guard is observing more than one event is counted. This time is $[2, 3]$, so the cost is $1$. This is quite unintuitive, but it is exactly what I describe in the question.  
> **username_1**: Ok! Now it's clear  
> **username_2**: 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.  

---

## 0 answers

