A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
<|reference_start|>A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line: In the online facility assignment on a line (OFAL) with a set $S$ of $k$ servers and a capacity $c:S\to\mathbb{N}$, each server $s\in S$ with a capacity $c(s)$ is placed on a line and a request arrives on a line one-by-one. The task of an online algorithm is to irrevocably assign a current request to one of the servers with vacancies before the next request arrives. An algorithm can assign up to $c(s)$ requests to each server $s\in S$.   In this paper, we show that the competitive ratio of the permutation algorithm is at least $k+1$ for OFAL where the servers are evenly placed on a line. This disproves the result that the permutation algorithm is $k$-competitive by Ahmed et al..<|reference_end|>
@article{harada2024a,
    title={A Lower Bound on the Competitive Ratio of the Permutation Algorithm for
  Online Facility Assignment on a Line},
    author={Tsubasa Harada},
    journal={arXiv preprint arXiv:2402.12734},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.12734},
    primaryClass={cs.DS cs.DM}
}