Obere Grenze auf der durchschnittlichen Anzahl von Überschneidungen für ein Intervall in einem Satz von Intervallen

Question

$ \ Mathcal {i} $ ein Satz von Intervallen mit Kardinalität $ L $ , wo jedes Intervall $ i_i \ in \ mathcal {i} $ von der Form $ [A_I, B_I] $ und $ A_I, B_i $ sind paarweise unterschiedliche nicht negative Ganzzahlen, die von einer konstanten $ C $ begrenzt sind dh $ 0 \ LEQ A_I . Wir sagen ein Paar von Intervallen $ i_i, i_j \ in \ matcal {i} $ Überlappung, wenn die Länge der Überlappung $ ist > 0 $ .

Definieren Sie eine Funktion $ F (i) $ , welche die Anzahl der Intervalle in $ \ Mathcal {i} \ berechnet \ Backslaslash i_i $ Dieses Intervall $ i_i $ Überlappungen mit. \ beginnen {Gleichung} F (i)=sum_ {j= 1, j \ neq i} ^ {l} Überlappung (i_i, i_j) \ end {Gleichung} Wo die Funktion $ Überlappung (i_i, i_j) $ ist eine Indikatorfunktion, die 1 wenn $ i_i, i_j $ Überlappung, sonst gibt es wieder 0.

Die durchschnittliche Anzahl von Überschneidungen für die Intervalle in $ \ Mathcal {i} $ , mit $ AVG (\ mathcal {i}) $ wird von $ avg (\ mathcal {i}) angegeben (\ mathcal {i})=dfrac {\ sum_ {i= 1} ^ {l} f (i )} {L} $ .

Die Frage ist, angenommen, wir dürfen die Intervalle in der Set $ \ Mathcal {i} $ mit den folgenden zusätzlichen Bedingungen auswählen:

.
1. für jeden $ t \ in [0, c] $ , wir haben höchstens $ m $ (und $ M ) Intervalle in $ \ Mathcal {i} $ so, dass $ T $ ist in diesen Invallen von $ M $ enthalten. Anders angegeben, höchstens $ M $ Intervalle überlappen sich zu einem beliebigen Zeitpunkt.
2. Jedes Intervall in $ \ Mathcal {i} $ Überschneidungen mit höchstens $ K $ Andere Intervalle und $ M .

dann, was ist eine obere Grenze auf $ avg (\ mathcal {i}) $ für jede Auswahl der Intervalle in $ \ Mathcal {I} $ Befriedigung 1, 2?

Falls Sie sich fragen, ist dieses Problem für mich von Interesse, um die Laufzeit eines Planungsalgorithmus studieren zu können.

Ich kann keine nicht-triviale obere Grenze für $ AVG (\ Mathcal {I}) $ aufstellen und wäre daran interessiert, wissen Sie, ob das Problem Ich habe gesagt, wurde untersucht. Ich bin auch offen für Ideen, wie man in der Lage sein kann, eine enge obere Grenze für $ AVG (\ Mathcal {I}) $ zu erhalten.

Answer 1

Wenn wir $ L $ ignorieren und nur auf die Parameter $ c, k, m $ ignorieren Die folgende obere Grenze ist asymptotisch eng, dh es geht um das Beste, was Sie tun können, bis zu einem konstanten Faktor:

$$ \ Text {AVG} (\ Mathcal {I}) \ le \ min (MC, K). $$

---

Beweis, dass es eine obere Grenze ist: Fixieren Sie ein beliebiges Intervall. Wir werden versprochen, dass es mit höchstens $ K $ andere überlappt. Das Intervall hat auch höchstens $ C $ Punkte darin, so dass wir von einer über diese Punkte gebundenen Union, also können wir auch mit höchstens $ MC $ andere. Daher überschneidet es mit höchstens $ \ min (mc, k) $ andere. Nun wird der Durchschnitt einer Reihe von Zahlen, die alle $ \ le \ min (MC, K) $ sind, selbst $ \ le \ min (mc, k) $ .

---

Beweis, dass es eng ist: Ich werde den Aufbau eines Satzes von Intervallen zeigen, in dem $ \ text {avg} (\ matcal {i}) \ SIM \ min (MC, K ) / 4 $ . Es gibt zwei Fälle:

.

• Fall 1: $ k \ ge MC $ . Verwenden Sie dann $ M / 2 $ Kopien jedes Intervalls des Formulars $ [i, i] $ ( dh jedes Länge-0-Intervall), und verwenden Sie $ M / 2 $ Kopien des Intervalls $ [1, C] $ . Sie können beobachten, dass letztere jeweils mit $ \ SIM MC / 2 $ andere Intervalle (und alle Kreuzungen mit weniger als $ K $ ). Daher ist der Durchschnitt um $ MC / 4 $ . Dies gibt eine Sammlung von Intervallen an, in denen jeder Punkt mit Invalle von $ M $ schneidet, jedes Intervall schneidet mit $ \ le k $ < / span> andere und $ \ text {avg} (\ mathcal {i}) \ SIM MC / 4=min (mc, k) / 4 $ .

• Fall 2: $ k . Set $ C '= K / M $ , wenden Sie den obigen Aufbau in das Intervall $ [1, c'] $ < / span> anstelle von $ [1, c] $ , und wir erhalten eine Sammlung von Intervallen, in denen jeder Punkt mit $ schneidet M $ Intervalle, jedes Intervall schneidet mit $ \ le k $ andere und $ \ text {avg} (\ Mathcal {I}) \ SIM MC '/ 4= k / 4=min (mc, k) / 4 $ .

---

Wenn Sie sich auch für die Abhängigkeit von $ L $ kümmern, können Sie möglicherweise auf der obigen Analyse aufbauen, um zu sehen, wie er von der $ L $ .