研究设施选址中多种目标的兼容性，发现可同时近似最优。
Compatibility of Max and Sum Objectives for Committee Selection and $k$-Facility Location
- 分析四种距离优化目标的组合兼容性
- 证明任意两目标存在同时接近最优的解
- 适用于多目标决策与委员会选人场景
我们研究度量空间中的设施选址问题（或等价的委员会选择问题），需在任意度量空间中选择k个设施以服务一组客户C。考虑四种不同目标：每位客户i试图最小化其到所选设施的距离之和或最大值，整体目标则为所有客户成本的和或最大值。不同于单一目标优化，本文研究这些目标之间的兼容性，证明了对于任意一对目标，均存在同时接近各自最优的解。结果表明，在选择设施或代表性委员会时，通常可构造出对多个目标都表现良好的方案，而无需牺牲某一目标以换取另一目标。
原文摘要 · Abstract (English)
We study a version of the metric facility location problem (or, equivalently, variants of the committee selection problem) in which we must choose $k$ facilities in an arbitrary metric space to serve some set of clients $C$. We consider four different objectives, where each client $i\in C$ attempts to minimize either the sum or the maximum of its distance to the chosen facilities, and where the overall objective either considers the sum or the maximum of the individual client costs. Rather than optimizing a single objective at a time, we study how compatible these objectives are with each other, and show the existence of solutions which are simultaneously close-to-optimum for any pair of the above objectives. Our results show that when choosing a set of facilities or a representative committee, it is often possible to form a solution which is good for several objectives at the same time, instead of sacrificing one desideratum to achieve another.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。