1
$\begingroup$

Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded by a constant $C$ i.e. $0 \leq a_i < b_i \leq C$. We say a pair of intervals $I_i, I_j \in \mathcal{I}$ overlap if the length of overlap is $> 0$.

Define a function $F(i)$ which computes the number of intervals in $\mathcal{I} \backslash I_i$ that interval $I_i$ overlaps with. \begin{equation} F(i) = \sum_{j=1, j \neq i}^{L} Overlap(I_i, I_j) \end{equation} where the function $Overlap(I_i, I_j)$ is an indicator function which returns 1 if $I_i, I_j$ overlap, else it returns 0.

The average number of overlaps for the intervals in $\mathcal{I}$, denoted by $Avg(\mathcal{I})$ is given by $Avg(\mathcal{I}) = \dfrac{\sum_{i=1}^{L}F(i)}{L}$.

The question is, suppose we are allowed to choose the intervals in the set $\mathcal{I}$ with the following additional conditions:

  1. For any $t \in [0, C]$, we have at most $M$ (and $M < L$) intervals in $\mathcal{I}$ such that $t$ is contained within those $M$ intervals. Stated differently, at most $M$ intervals overlap at any point in time.
  2. Any interval in $\mathcal{I}$ overlaps with at most $K$ other intervals, and $M < K < L$.

then, what is an upper bound on $Avg(\mathcal{I})$ for any choice of the intervals in $\mathcal{I}$ satisfying 1, 2?

In case you are wondering, this problem is of interest to me in order to be able to study the run-time of a scheduling algorithm.

I am unable to come up with a non-trivial upper bound for $Avg(\mathcal{I})$ and would be interested to know if the problem I stated has been studied. I am also open to ideas on how one may be able to obtain a tight upper bound for $Avg(\mathcal{I})$.

$\endgroup$
  • $\begingroup$ What's the best upper bound you have so far? What's the best lower bound you have so far? (i.e., explicit construction of a set of intervals that makes Avg(I) as large as possible) $\endgroup$ – D.W. Jan 6 at 18:22
0
$\begingroup$

If we ignore $L$ and focus only on the parameters $C,K,M$, the following upper bound is asymptotically tight, i.e., it's about the best you can do, up to a constant factor:

$$\text{Avg}(\mathcal{I}) \le \min(MC,K).$$


Proof that it's an upper bound: Fix any interval. We're promised that it overlaps with at most $K$ others. Also, the interval has at most $C$ points in it, so by a union bound over those points, we can also infer it overlaps with at most $MC$ others. Therefore, it overlaps with at most $\min(MC,K)$ others. Now the average of a bunch of numbers that are all $\le \min(MC,K)$ will itself be $\le \min(MC,K)$.


Proof that it's tight: I will show the construction of a set of intervals where $\text{Avg}(\mathcal{I}) \sim \min(MC,K)/4$. There are two cases:

  • Case 1: $K \ge MC$. Then use $M/2$ copies of each interval of the form $[i,i]$ (i.e., each length-0 interval), and use $M/2$ copies of the interval $[1,C]$. You can observe that the latter each intersect with $\sim MC/2$ other intervals (and all intersect with fewer than $K$). So, the average is about $MC/4$. This gives a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC/4 = \min(MC,K)/4$.

  • Case 2: $K < MC$. Set $C' = K/M$, apply the above construction to the interval $[1,C']$ instead of $[1,C]$, and we obtain a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC'/4 = K/4 = \min(MC,K)/4$.


If you also care about the dependence on $L$, you might be able to build on the above analysis to see how it might depend on $L$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.