We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line exceeds √log2(n+1)/15 for all n = 2i-1 : i ∈ N, settling a 25-year-old open question.
Matching on the line admits no o(√log n)-competitive algorithm
Peserico E.;Scquizzato M.
2021
Abstract
We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line exceeds √log2(n+1)/15 for all n = 2i-1 : i ∈ N, settling a 25-year-old open question.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
LIPIcs-ICALP-2021-103.pdf
accesso aperto
Tipologia:
Published (publisher's version)
Licenza:
Creative commons
Dimensione
534.05 kB
Formato
Adobe PDF
|
534.05 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
