الحد الأعلى لمتوسط ​​عدد التداخلات لفاصل زمني ضمن مجموعة من الفواصل الزمنية

Question

يترك $\mathcal{I}$ تكون مجموعة من الفواصل الزمنية مع الكاردينالية $ل$, ، حيث كل فاصل زمني $I_i \in \mathcal{I}$ هو من النموذج $[a_i, b_i]$ و $أ_ي، ب_ي$ هي أعداد صحيحة غير سالبة متمايزة ويحدها ثابت $ج$ أي. $0 \leq a_i < b_i \leq C$.نقول زوج من الفواصل الزمنية $I_i, I_j \in \mathcal{I}$ التداخل إذا كان طول التداخل $> 0$.

تحديد وظيفة $F(ط)$ الذي يحسب عدد الفواصل الزمنية في $\mathcal{I} \الشرطة المائلة العكسية I_i$ تلك الفاصلة $I_i$ يتداخل مع.\begin{equation} F(i) = \sum_{j=1, j eq i}^{L} Overlap(I_i, I_j) \ النهاية {المعادلة}حيث الوظيفة $التداخل (I_i، I_j)$ هي وظيفة مؤشر تقوم بإرجاع 1 إذا $I_i، I_j$ تتداخل، وإلا فإنها ترجع 0.

متوسط ​​عدد التداخلات للفواصل الزمنية $\mathcal{I}$, ، يشار إليه ب $متوسط(\mathcal{I})$ اعطي من قبل $Avg(\mathcal{I}) = \dfrac{\sum_{i=1}^{L}F(i)}{L}$.

السؤال هو، لنفترض أنه مسموح لنا باختيار الفترات في المجموعة $\mathcal{I}$ بالشروط الإضافية التالية:

1. لأي $t \في [0، C]$, ، لدينا على الأكثر $م$ (و $م <ل$) فواصل في $\mathcal{I}$ مثل ذلك $t$ موجود ضمن تلك $م$ فترات.وذكر بشكل مختلف، على الأكثر $م$ تتداخل الفواصل الزمنية في أي وقت.
2. أي فاصل في $\mathcal{I}$ يتداخل مع على الأكثر $ك$ فترات أخرى، و $M <K <L$.

ثم، ما هو الحد الأعلى على $متوسط(\mathcal{I})$ لأي اختيار من الفواصل الزمنية في $\mathcal{I}$ مرضية 1، 2؟

في حال كنت تتساءل، فهذه المشكلة تهمني حتى أتمكن من دراسة وقت تشغيل خوارزمية الجدولة.

أنا غير قادر على التوصل إلى حد أعلى غير تافه ل $متوسط(\mathcal{I})$ وسيكون مهتمًا بمعرفة ما إذا كانت المشكلة التي ذكرتها قد تمت دراستها.أنا أيضًا منفتح على الأفكار حول كيفية الحصول على حد أعلى محكم $متوسط(\mathcal{I})$.

Answer 1

إذا تجاهلنا $ل$ والتركيز فقط على المعلمات $ج، ك، م $, ، الحد الأعلى التالي ضيق بشكل غير مقارب، أي أنه يتعلق بأفضل ما يمكنك القيام به، حتى عامل ثابت:

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

---

والدليل على أنه حد أعلى:إصلاح أي فاصل زمني.لقد وعدنا أنه يتداخل مع على الأكثر $ك$ آحرون.أيضا، الفاصل الزمني على الأكثر $ج$ النقاط الموجودة فيه، لذلك من خلال اتحاد مقيد فوق تلك النقاط، يمكننا أيضًا أن نستنتج أنه يتداخل مع الحد الأقصى $MC$ آحرون.ولذلك، فإنه يتداخل مع على الأكثر $\دقيقة(MC,K)$ آحرون.الآن متوسط ​​مجموعة من الأرقام كلها $\le \min(MC,K)$ سوف يكون في حد ذاته $\le \min(MC,K)$.

---

دليل على أنه ضيق:وسوف تظهر بناء مجموعة من الفواصل الزمنية حيث $ ext{متوسط}(\mathcal{I}) \sim \min(MC,K)/4$.هناك حالتان:

• حالة 1: $K \ge MC$.ثم استخدام $م/2$ نسخ من كل فترة من النموذج $[أنا،أنا]$ (أي كل فترة زمنية 0)، والاستخدام $م/2$ نسخ من الفاصل الزمني $[1,C]$.يمكنك ملاحظة أن كل هذا الأخير يتقاطع مع $\سيم MC/2$ فترات أخرى (وكلها تتقاطع مع أقل من $ك$).لذا فإن المتوسط ​​حوالي $MC/4$.وهذا يعطي مجموعة من الفواصل الزمنية التي تتقاطع معها كل نقطة $م$ فترات، كل فترة تتقاطع مع $\لو ك$ الآخرين، و $ ext{Avg}(\mathcal{I}) \sim MC/4 = \min(MC,K)/4$.

• الحالة 2: $K <MC$.تعيين $C' = K/M$, ، قم بتطبيق البناء أعلاه على الفاصل الزمني $[1,C']$ بدلاً من $[1,C]$, ، وحصلنا على مجموعة من الفواصل الزمنية التي تتقاطع معها كل نقطة $م$ فترات، كل فترة تتقاطع مع $\لو ك$ الآخرين، و $ ext{Avg}(\mathcal{I}) \sim MC'/4 = K/4 = \min(MC,K)/4$.

---

إذا كنت تهتم أيضًا بالاعتماد على $ل$, ، قد تتمكن من البناء على التحليل أعلاه لترى كيف يمكن أن يعتمد عليه $ل$.