We prove that the 2n−1 lower bound on the competitive ratio of the PERMUTATION algorithm for online metric matching with n servers holds even if the number m of distinct servers is as low as 4, and even on the line, a simple space where lower competitive ratios are often possible. The same technique yields a [Formula presented.] lower bound on the competitive ratio of PERMUTATION in the special case of n/m servers at each of m evenly-spaced points on the line, improving for all m > 4 a recent m+1 lower bound and disproving its conjectured optimality.
PERMUTATION for online metric matching with m distinct servers
Peserico E.;Scquizzato M.
2026
Abstract
We prove that the 2n−1 lower bound on the competitive ratio of the PERMUTATION algorithm for online metric matching with n servers holds even if the number m of distinct servers is as low as 4, and even on the line, a simple space where lower competitive ratios are often possible. The same technique yields a [Formula presented.] lower bound on the competitive ratio of PERMUTATION in the special case of n/m servers at each of m evenly-spaced points on the line, improving for all m > 4 a recent m+1 lower bound and disproving its conjectured optimality.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
