Limite superiore sul numero medio di sovrapposizioni per un intervallo all'interno di un insieme di intervalli

Question

Let $ \ Mathcal {i} $ essere un insieme di intervalli con cardinalità $ l $ , dove ogni intervallo $ i_i \ in \ mathcal {i} $ è del modulo $ [a_i, b_i] $ e $ a_i, b_i $ sono numeri interi non negativi distinti a coppie delimitati da una costante $ c $ cioè $ 0 \ leq a_i . Diciamo un paio di intervalli $ i_i, i_j \ in \ mathcal {i} $ si sovrappongono se la lunghezza della sovrapposizione è $ > 0 $ .

Definisci una funzione $ f (i) $ che calcola il numero di intervalli in $ \ mathcal {i} \ Backslash I_i $ Quell'intervallo $ i_i $ si sovrappone a. \ Begin {equation} F (i)=sum_ {j= 1, j \ neq I} ^ {l} Sovrapposizione (i_i, i_j) \ end {equation} dove la funzione $ sovrapposizione (i_i, i_j) $ è una funzione di indicatore che restituisce 1 se $ i_i, i_j $ Sovrapposizione, altrimenti restituisce 0.

Il numero medio di sovrapposizioni per gli intervalli in $ \ mathcal {i} $ , denotato da $ AVG (\ Mathcal {i}) $ è dato da $ avg (\ mathcal {i})=dfrac {\ sum_ {i= 1} ^ {l} f (i )} {L} $ .

La domanda è, supponiamo che ci sia consentito scegliere gli intervalli nel set $ \ mathcal {i} $ con le seguenti condizioni aggiuntive:

.
1. per qualsiasi classe $ t \ in [0, c] $ , abbiamo al massimo $ m $ (e $ m ) intervalli in $ \ mathcal {i} $ tale che $ T $ è contenuto all'interno di quelle $ m $ intervalli. Dichiarato in modo diverso, al massimo $ m $ gli intervalli si sovrappongono in qualsiasi momento.
2. qualsiasi intervallo in $ \ mathcal {i} $ si sovrappone alla maggior parte dei $ k $ altri intervalli e $ m .

quindi, cos'è un limite superiore su $ avg (\ mathcal {i}) $ per qualsiasi scelta degli intervalli in $ \ Mathcal {i} $ soddisfacente 1, 2?

Nel caso in cui ti chiedi, questo problema è di interesse per me per poter studiare il tempo di esecuzione di un algoritmo di pianificazione.

Non riesco a trovare un limite superiore non banale per $ avg (\ mathcal {i}) $ e sarebbe interessato a sapere se il problema Ho affermato che è stato studiato. Sono anche aperto alle idee su come si può essere in grado di ottenere un limite superiore stretto per $ avg (\ mathcal {i}) $ .

Answer 1

Se ignoriamo $ l $ e focalizza solo sui parametri $ c, k, m $ , il seguente limite superiore è asintoticamente stretto, cioè, è il meglio che puoi fare, fino a un fattore costante:

$$ \ text {avg} (\ mathcal {i}) \ le \ min (mc, k). $$

---

.

Prova che è un limite superiore: fissa qualsiasi intervallo. Abbiamo promesso che si sovrappresse con la maggior parte dei $ k $ altri. Inoltre, l'intervallo ha al massimo $ c $ punti in esso, quindi da un sindacato legato su quei punti, possiamo anche dedurre sovrapponirsi con la maggior parte dei $ MC $ Altri. Pertanto, si sovrappone alla maggior parte dei $ \ min (mc, k) $ altri. Ora la media di un gruppo di numeri che sono tutte $ \ le \ min (mc, k) $ sarà $ \ Le \ min (mc, k) $ .

---

.

Prova che è stretto: mostrerò la costruzione di un insieme di intervalli in cui $ \ text {avg} (\ mathcal {i}) \ sim \ min (mc, k ) / 4 $ . Ci sono due casi:

.

• Caso 1: $ k \ ge mc $ . Quindi utilizzare $ M / 2 $ copie di ciascun intervallo del modulo $ [i, i] $ ( cioè ogni intervallo di lunghezza-0) e utilizzare $ m / 2 $ copie dell'intervallo $ [1, c] $ . È possibile osservare che quest'ultimo si interseca con $ \ SIM MC / 2 $ altri intervalli (e tutto intersecano con meno di $ K $ ). Quindi, la media è circa $ MC / 4 $ . Questo fornisce una raccolta di intervalli in cui ogni punto si interseca con $ m $ intervalli, ogni intervallo interseca con $ \ le k $ < / span> Altri e $ \ text {avg} (\ mathcal {i}) \ SIM MC / 4=min (MC, K) / 4 $ .

• Caso 2: $ k . Imposta $ c '= k / m $ , applicare la costruzione di cui sopra all'intervallo $ [1, c'] $ < / span> invece di $ [1, c] $ , e otteniamo una raccolta di intervalli in cui ogni punto si interseca con $ M $ intervalli, ogni intervallo si interseca con $ \ le k $ altri e $ \ text {avg} (\ Mathcal {i}) \ SIM MC '/ 4= K / 4=min (mc, k) / 4 $ .

---

.

Se ti interessa anche la dipendenza da $ l $ , potresti essere in grado di costruire sull'analisi di cui sopra per vedere come potrebbe dipendere dalla classe $ L $ .