在一组间隔内的间隔内的平均重叠数上的上限

Question

let $ \ mathcal {i} $ 是一组与基数 $ l $ ，其中每个间隔 $ i_i \ in \ mathcal {i} $ 是 $ [a_i，b_i] $ 和 $ a_i，b_i $ 是由常量 $ c $ 的成对不同的非负整数IE $ 0 \ Leq A_I 。我们说一对间隔 $ i_i，i_j \ in \ mathcal {i} $ 如果重叠长度是 $ > 0 $ 。

定义一个函数 $ f（i）$ ，它计算 $ \ mathcal {i} \中的间隔数backslash i_i $ 那个间隔 $ i_i $ 重叠。 \ begin {公式} f（i）=sum_ {j= 1，j \ neq i} ^ {l}重叠（i_i，i_j） \结束{公式} 其中函数 $重叠（i_i，i_j）$ 是一个指示函数，如果 $ i_i，i_j $ 重叠，否则它返回0。

$ \ mathcal {i} $ 中的间隔的平均重叠次数，由 $ avg表示（\ mathcal {i}）$ 由 $ avg（\ mathcal {i}）=dfrac {\ sum_ {i= 1} ^ {l} f（i ）}} {l} $ 。

问题是，假设我们被允许在SET $ \ MATHCAL {i} $ 中选择以下间隔：

1. 对于任何 $ t \在[0，c] $ 中，我们最多是 $ m $ （和 $ m $ \ mathcal {i} $ 这样的 $ T $ 包含在 $ m $ 间隔内。不同地说，大多数<跨度类=“数学集装箱”> $ M $ 间隔在任何时间点都重叠。
2. $ \ mathcal {i} $ 以大多数 $ k $ 其他间隔重叠，以及 $ m 。

然后，什么是 $ avg（\ mathcal {i}）$ 的上限，用于 $ \ mathcal {i} $ 满足1,2？

如果您想知道，此问题对我来说是有意义的，以便能够研究调度算法的运行时间。

我无法提出 $ avg（\ mathcal {i}）$ ，并且有兴趣知道是否存在问题我曾经研究过。我也对如何能够获得 $ Avg（\ Mathcal {i}）$ 的紧密上限的想法。

Answer 1

如果我们忽略 $ l $ 并且只关注参数 $ c，k，m $ ，以下上限是渐近的，即，它是你能做的最好的，直到一个恒定因素：

$$ \ text {avg}（\ mathcal {i}）\ le \ min（mc，k）。$$

---

证明它是一个上限：修复任何间隔。我们承诺它与大多数 $ k $ 其他相反。此外，间隔具有大多数 $ c $ 点，因此由一个union绑定在这些点上，我们也可以推断它与大多数 $ MC $ 其他。因此，它与大多数 $ \ min（mc，k）$ 其他重叠。现在，所有 $ \ le \ min（mc，k）$ 本身都是 $ \ Le \ min（mc，k）$ 。

---

证明它是紧的：我将显示一组间隔的构造，其中 $ \ text {avg}（\ mathcal {i}）\ sim \ min（mc，k / 4 $ 。有两种情况：

• 案例1： $ k \ ge mc $ 。然后使用 $ m / 2 $ 表单 $ [i，i] $ 的每个间隔的副本IE，每个长度-0间隔），并使用 $ m / 2 $ 拷贝的时间间隔 $ [1，c] $ 。您可以观察到后者每个与 $ \ sim mc / 2 $ 其他间隔（以及少于 $ K $ ）。因此，平均值是关于 $ mc / 4 $ 。这给出了一个间隔的集合，其中每个点与 $ m $ 间隔相交，每个间隔与 $ \ le k $ < / span>其他， $ \ text {avg}（\ mathcal {i}）\ sim mc / 4=min（mc，k）/ 4 $ 。

• 案例2： $ k 。 set $ c'= k / m $ ，将上面的构造应用于间隔 $ [1，c'] $ < / span>而不是 $ [1，c] $ ，并且我们获得一个间隔的集合，其中每个点与 $相交M $ 间隔，每个间隔与 $ \ le k $ 其他，以及 $ \ text {avg} （\ mathcal {i}）\ sim mc'/ 4= k / 4= min（mc，k）/ 4 $ 。

---

如果您还关心对 $ l $ 的依赖，您可能可以在上面的分析上构建，看看它如何依赖于 $ l $ 。