Limite supérieure sur le nombre moyen de chevauchements pour un intervalle dans un ensemble d'intervalles

Question

let $ \ mathcal {i} $ soit un ensemble d'intervalles avec cardinalité $ l $ , où chaque intervalle $ i_i \ in \ mathcal {i} $ est de la forme $ [A_I, B_I] $ et $ a_i, b_i $ sont des entiers non négatifs distincts par paires délimités par une constante $ C $ Ie $ 0 \ LEQ A_I . Nous disons une paire d'intervalles $ i_i, i_j \ in \ mathcal {i} $ $ se chevauchent si la longueur de chevauchement est $ > 0 $ .

définir une fonction $ f (i) $ qui calcule le nombre d'intervalles dans $ \ mathcal {i} \ backslash i_i $ cet intervalle $ i_i $ chevauche avec. \ commence {équation} F (i)=sum_ {j= 1, j \ neq i} ^ {l} chevauchement (i_i, i_j) \ fin {équation} où la fonction $ chevauchement (i_i, i_j) $ est une fonction indicateur qui retourne 1 si $ i_i, i_j $ chevauchement, sinon il retourne 0.

Le nombre moyen de chevauchements pour les intervalles dans $ \ mathcal {i} $ , noté par $ avg (\ mathcal {i}) $ est donné par $ avg (\ mathcal {i})=dfrac {\ sum_ {i= 1} ^ {l} f (i )} {L} $ .

La question est, supposons que nous soyons autorisés à choisir les intervalles dans l'ensemble $ \ mathcal {i} $ avec les conditions supplémentaires suivantes:

1. pour tout $ t \ in [0, c] $ , nous avons au plus $ m $ (et $ m ) intervalles dans $ \ mathcal {i} $ telle que $ t $ est contenu dans ces $ M $ intervalles. Indiqué différemment, au plus $ M $ se chevauchent à tout moment.
2. tout intervalle dans $ \ mathcal {i} $ se chevauche avec au plus $ k $ autres intervalles et $ m .

alors, quelle est une limite supérieure sur $ avg (\ mathcal {i}) $ pour tout choix des intervalles dans $ \ mathcal {i} $ satisfaisant 1, 2?

Si vous vous demandez, ce problème me intéresse afin de pouvoir étudier le temps d'exécution d'un algorithme de planification.

Je suis incapable de trouver une limite supérieure non triviale pour $ avg (\ mathcal {i}) $ et serait intéressé à savoir si le problème J'ai été déclaré a été étudié. Je suis également ouvert aux idées sur la manière dont on peut être capable d'obtenir une limite supérieure serrée pour $ avg (\ mathcal {i}) $ .

Answer 1

Si nous ignorons $ l $ et concentrez uniquement sur les paramètres $ C, k, m $ , la limite supérieure suivante est serrée asymptotique, c'est-à-dire que c'est à peu près le mieux que vous puissiez faire, jusqu'à un facteur constant:

$$ \ texte {avg} (\ mathcal {i}) \ Le \ min (mc, k). $$

---

Preuve que c'est une limite supérieure: réparer tout intervalle. Nous avons promis que cela se chevauche avec au plus $ K $ Autres. En outre, l'intervalle a au plus $ C $ C $ Les points, de sorte que par un syndicat lié sur ces points, nous pouvons également en déduire qu'il chevauche au plus $ MC $ Autres. Par conséquent, il chevauche avec la plupart des $ \ min (mc, k) $ autres. Maintenant, la moyenne d'un tas de nombres qui sont tous $ \ le \ min (mc, k) $ sera lui-même $ \ le \ min (mc, k) $ .

---

Preuve que c'est serré: je montrerai la construction d'un ensemble d'intervalles où $ \ text {avg} (\ mathcal {i}) \ sim \ min (mc, k ) / 4 $ . Il y a deux cas:

• Case 1: $ K \ GE MC $ . Ensuite, utilisez $ M / 2 $ Copies de chaque intervalle du formulaire $ [I, I] $ ( C'est-à-dire que chaque intervalle de longueur 0) et utilisent $ m / 2 $ copies de l'intervalle $ [1, c] $ . Vous pouvez observer que ces derniers se croisent avec $ \ sim mc / 2 $ autres intervalles (et tous les intersect avec moins de $ K $ ). Donc, la moyenne est sur $ MC / 4 $ . Cela donne une collection d'intervalles dans lesquels chaque point se coupe avec $ M $ , chaque intervalle se coupe avec $ \ LE K $ < / Span> Autres et $ \ TEXT {AVG} (\ MATHCAL {I}) \ SIM MC / 4=min (mc, k) / 4 $ .

• cas 2: $ k . SET $ C '= K / M $ , Appliquez la construction ci-dessus à l'intervalle $ [1, C'] $ < / span> au lieu de $ [1, c] $ , et nous obtenons une collection d'intervalles où chaque point se coupe avec $ M $ intervalles, chaque intervalle se coupe avec $ \ le k $ autres et $ \ text {avg} (\ mathcal {i}) \ sim mc '/ 4= k / 4=min (mc, k) / 4 $ .

---

Si vous vous souciez également de la dépendance à la dépendance $ l $ , vous pourriez peut-être construire sur l'analyse ci-dessus pour voir comment cela pourrait dépendre de $ l $ .