具有异常值的容错k-供应商模型

本文提出FkSO问题的近似算法，结合round-or-cut方法与LP松弛，在t种容错水平下获得(4t?1)-近似比，t=1时优化至3-近似，优于现有结果。

　　

摘要

摘要

我们提出了针对容错型“k-供应商含异常值”（F_kSO）问题的近似算法。这是两个已知问题的常见泛化形式：“k-供应商含异常值”问题和“容错型k-供应商”问题，这两个问题又分别是对经典“k-供应商”问题的扩展。在“k-供应商”问题中，目标是从一组可能的设施集合F中选择k个设施来服务n个客户C；目标函数表示任何客户到达开放设施所需行驶的最远距离。而在F_kSO问题中，每个客户v都有一个容错度?_v，现在每个客户希望有?_v个设施为其服务；因此，每个客户v对目标函数的贡献就是它到第?_v个开放设施的距离。此外，我们可以选择m个客户来提供服务，只有这些客户会对目标函数产生影响，而剩下的n - m个客户被视为异常值。

我们的主要成果是对F_kSO问题提供了一个(4^t - 1)的近似算法，其中t是实例中出现的不同?_v值的数量。当t = 1，即所有?_v值都相同时，该算法达到了3的近似精度，这改进了Inamdar和Varadarajan在2020年提出的统一情况下的11近似算法。我们对统一情况的结果与现有的“k-供应商”、“k-供应商含异常值”以及“容错型k-供应商”问题的紧密3近似结果相匹配。

我们的关键技术贡献是将“round-or-cut”方案应用于F_kSO问题。通过线性规划（LP）松弛方法，我们将问题简化为一个更简单的优化问题，从而能够得到“round”步骤的距离界限和“cut”步骤的有效不等式。通过改变简化问题的方式，我们可以得到不同的距离界限——我们提出了一个变体算法，对于t ∈ {2, 3}的情况，该算法能够达到(2^t + 1)的近似精度。另外，当t = 1时，我们提供了一个更直接的“round-or-cut”应用方法，得到的3近似精度比我们的通用算法更为简单。

人工智能摘要

人工智能生成的摘要（实验性）

此摘要是使用自动化工具生成的，并非由文章作者编写或审核。它旨在帮助读者发现研究内容的相关性，并协助来自相关研究领域的读者理解本文。它是对作者提供的摘要的补充，作者提供的摘要仍是文章的官方总结。完整文章才是权威版本。点击此处了解更多。

点击此处对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的摘要版本。

要查看此人工智能生成的简单语言摘要，您需要拥有高级访问权限。