Narrow Results

In the online metric matching problem, there are servers on a given metric space and requests are given one-by-one. The task of an online algorithm is to match each request immediately and irrevocably with one of the unused servers. In this paper, we pursue competitive analysis for two variants of the online metric matching problem. The first variant is a restriction where each server is placed at one of two positions, which is denoted by OMM($2$). We show that a simple greedy algorithm achieves the competitive ratio of 3 for OMM($2$). We also show that this greedy algorithm is optimal by showing that the competitive ratio of any deterministic online algorithm for OMM($2$) is at least 3. The second variant is the online facility assignment problem on a line. In this problem, the metric space is a line, the servers have capacities, and the distances between any two consecutive servers are the same. We denote this problem by OFAL($k$), where $k$ is the number of servers. We first observe that the upper and lower bounds for OMM($2$) also hold for OFAL($2$), so the competitive ratio for OFAL($2$) is exactly 3. We then show lower bounds on the competitive ratio $1+\sqrt{6}$$(>3.44948)$, $\frac{4+\sqrt{73}}{3}$$(>4.18133)$ and $\frac{13}{3}$$(>4.33333)$ for OFAL($3$), OFAL($4$) and OFAL($5$), respectively.

In the online facility assignment problem $\mathrm{\text{OFA}}(k,{\{c_i\}}_{i=1}^k)$, there exist $k$ servers $s_1,\dots ,s_k$ on a metric space where each $s_i$ has an integer capacity $c_i$ and a request arrives one-by-one. The task of an online algorithm is to irrevocably match a current request with one of the servers with vacancies before the next request arrives. As special cases for $\mathrm{\text{OFA}}(k,{\{c_i\}}_{i=1}^k)$, we consider $\mathrm{\text{OFA}}(k,{\{c_i\}}_{i=1}^k)$on a line , which is denoted by $\mathrm{\text{OFAL}}(k,{\{c_i\}}_{i=1}^k)$ and ${\mathrm{\text{OFAL}}}_{\mathrm{\text{eq}}}(k,{\{c_i\}}_{i=1}^k)$, where the latter is the case of $\mathrm{\text{OFAL}}(k,{\{c_i\}}_{i=1}^k)$ with equidistant servers. In this paper, we perform the competitive analysis for the above problems. As a natural generalization of the greedy algorithm grdy, we introduce a class of algorithms called MPFS (Most Preferred Free Servers) and show that any MPFS algorithm has the capacity-insensitive property, i.e., for any MPFS algorithm alg for $\mathrm{\text{OFA}}(k,{\{c_i\}}_{i=1}^k)$, if alg is $c$-competitive when $c_1=\cdots =c_k=1$, then alg is $c$-competitive for general ${\{c_i\}}_{i=1}^k$. By applying the capacity-insensitive property of the greedy algorithm grdy, we derive the matching upper and lower bounds $4k-5$ on the competitive ratio of grdy for ${\mathrm{\text{OFAL}}}_{\mathrm{\text{eq}}}(k,{\{c_i\}}_{i=1}^k)$. To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm alg for ${\mathrm{\text{OFAL}}}_{\mathrm{\text{eq}}}(k,{\{c_i\}}_{i=1}^k)$ is at least $2k-1$. Then, we propose a new MPFS algorithm idas (Interior Division for Adjacent Servers) for $\mathrm{\text{OFAL}}(k,{\{c_i\}}_{i=1}^k)$ and show that the competitive ratio of idas for ${\mathrm{\text{OFAL}}}_{\mathrm{\text{eq}}}(k,{\{c_i\}}_{i=1}^k)$ is at most $2k-1$, i.e., idas for ${\mathrm{\text{OFAL}}}_{\mathrm{\text{eq}}}(k,{\{c_i\}}_{i=1}^k)$ is best possible in all the MPFS algorithms. We also give numerical experiments to investigate the performance of idas and grdy and show that idas performs better than grdy for distribution of request sequences with locality.