论文标题
在线设施分配问题的容量不敏感算法
Capacity-Insensitive Algorithms for Online Facility Assignment Problems on a Line
论文作者
论文摘要
在“在线设施分配问题”（k，\ ell）中，存在k服务器，其能力\ ell \ geq 1在公制空间上，请求逐一到达。在线算法的任务是不可撤销地将当前请求与下一个请求到达之前的空缺的服务器之一。作为OFA（k，\ ell）的特殊情况，我们在一条线上考虑Ofa（k，\ ell），该行被ofal（k，\ ell）和ofal_ {eq}（k，\ ell）表示，其中后者是Al（K，\ ell）的情况，该案例是用平等的服务员。在本文中，我们处理上述问题的竞争分析。作为贪婪算法怪异的自然概括，我们介绍了一种称为MPFS（最优选的免费服务器）的算法，并表明任何MPFS算法具有对容量不敏感的属性，即，对于任何\ ell \ ell \ ellg geq 1，alg a alg对a（k，k，k，k，k，k，k，k，k，k compective as c-comptive at c c c c c comptive fora is comptive at comptive at compectife fora（k）iff als f ell（k compect）iff als f ell f。通过应用贪婪算法Grdy的容量不敏感特性，我们在Grdy的竞争比上得出了匹配的上限和下限4K-5，for Al_ {eq}（k，\ ell）。为了调查MPFS算法的能力，我们表明，对于Ofal_ {eq}（k，\ ell），任何MPFS算法ALG的竞争比率至少为$ 2K-1 $。 Then we propose a new MPFS algorithm IDAS (Interior Division for Adjacent Servers) for OFAL(k,\ell) and show that the competitive ratio of IDAS for OFAL}_{eq}(k,\ell) is at most 2k-1, i.e., IDAS for OFAL_{eq}(k,\ell) is best possible in all the MPFS algorithms.
In the online facility assignment problem OFA(k,\ell), there exist k servers with a capacity \ell \geq 1 on a metric space 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 OFA(k,\ell), we consider OFA(k,\ell) on a line, which is denoted by OFAL(k,\ell) and OFAL_{eq}(k,\ell), where the latter is the case of OFAL(k,\ell) with equidistant servers. In this paper, we deal with 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 \ell \geq 1, ALG is c-competitive for OFA(k,1) iff ALG is c-competitive for OFA(k,\ell). 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 OFAL_{eq}(k,\ell). To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm ALG for OFAL_{eq}(k,\ell) is at least $2k-1$. Then we propose a new MPFS algorithm IDAS (Interior Division for Adjacent Servers) for OFAL(k,\ell) and show that the competitive ratio of IDAS for OFAL}_{eq}(k,\ell) is at most 2k-1, i.e., IDAS for OFAL_{eq}(k,\ell) is best possible in all the MPFS algorithms.
