公平k-center问题近似难度的研究

《Information and Computation》:On the hardness of approximation of the fair k-center problem

【字体: 大 中 小 】 时间:2026年08月29日 来源:Information and Computation 1.4

编辑推荐:

  在本文中,研究人员研究了公平k-center问题(fair k-center problem)的近似硬度。在该问题中,给定一个度量空间(metric space)中的数据集,该数据集被划分为若干组,任务是选择k个数据点作为中心(centers),使得每个组中有

  
在本文中,研究人员研究了公平k-center问题(fair k-center problem)的近似硬度。在该问题中,给定一个度量空间(metric space)中的数据集,该数据集被划分为若干组,任务是选择k个数据点作为中心(centers),使得每个组中有规定数量的数据点被选中,同时最小化任意点到其最近中心的最大距离。尽管在一般度量空间下公平k-center存在多项式时间3-近似算法(3-approximation),但这一近似保证是否紧致或能否进一步改进一直悬而未决,尤其是经典无约束k-center问题(unconstrained k-center problem)存在多项式时间2-近似。研究人员通过证明,在假设P≠NP下,对任意ε>0,不存在多项式时间算法能将公平k-center近似到(3?ε)因子,从而解决了该开放问题。研究人员的不可近似结果即使在仅存在两个不相交组且每组至少选一个中心的情形下也成立,并扩展到含k个组的典型每组建一中心(one-per-group)设定(k任意)。因此,一般度量空间中公平k-center的因子3壁垒是固有的,现有3-近似算法即便在这些受限情形下也达到低阶项最优。该结果与k-supplier公式形成鲜明对比,后者无约束与公平变体均存在多项式时间3-近似。
研究背景方面,聚类是数据分析与优化的基础问题,k-center以最小化最大覆盖距离为目标,体现 egalitarian fairness 式最坏情况保护;当数据带敏感属性分组时,标准聚类会产生偏代表,故公平k-center要求中心集含各组规定数目的代表点。无约束k-center有多项式时间2-近似且近似紧致,而公平k-center仅有已知3-近似,公平性是否强制更差近似因子成开放问题;k-supplier变体中公平与否均为3-近似紧致,进一步凸显k-center的差异。研究人员旨在判定该差距是计算壁垒还是算法技术局限。论文发表于《Information and Computation》。
关键技术方法上,研究人员基于带开销的k-center(k-center with costs)的不可近似性(Chuzhoy等人定理:因子(3?ε)难近似),将其归约到禁选中心k-center(k-center with forbidden centers,点集分A∪B,中心仅许开在A,B点仍须被服务),再视为两组建模的公平k-center特例(G1=A,r1=k; G2=B,r2=0)获退化情形(3?ε)难近似;进而构造非退化归约覆盖两组成立(每组至少一中心)及任意组数每组建一中心(one-per-group)情形,从而将硬度由允许零需求推广到1≤ri≤k?1与恰一中心每组的实用公平设定。
研究结果部分,按原文小节叙述如下。第1节引言梳理公平k-center定义、算法侧因子3由来(Gonzalez贪婪得2-近似候选,匹配投影满足组约束得总3-近似)及与k-supplier区别;点明开放问题为因子3是否可改进。技术挑战段说明以k-center with costs的(3?ε)硬度为基,经forbidden centers特例得退化下界,但退化允许整组零代表不合实际公平,故需推至每组建正代表的非退化体制。贡献段给出研究人员结论:在两组各至少一中心、及k组每组建一中心两非退化设定下,公平k-center均(3?ε)难近似(P≠NP),故多项式时间因子3近似本质最优。第2节问题定义形式化公平k-center(度量空间(U,d),|U|=n,t组??={G1,…,Gt},Gi∩Gj=?,∪i∈[t]Gi=U,需求ri∈[1,k?1]或每组建一)。第3节硬度结果给出上述两设定的(3?ε)不可近似证明框架。第4节相关工作比对k-median/k-means/k-supplier在one-per-group归约下的近似保持性,突显k-center因每点兼客户与候选中心致壁垒。第5节结论讨论度规结构(Euclidean、doubling metrics)或放松公平约束为未来方向。
讨论与结论翻译:研究人员断定一般度量空间公平k-center的因子3近似屏障是内在的,现存的多项式时间3-近似算法在只含两组(每组至少一中心)与任意组数每组建一中心的非退化体制下均低阶项最优;该不可近似性由k-center with costs的(3?ε)硬度经forbidden-center特例与非退化归约确立。结果澄清公平约束本身在k-center中强制比无约束2-近似更严的3-近似极限,而在k-supplier中公平不引入额外间隙;意义在于为公平聚类算法设计划定界限,指引后续利用欧氏/翻倍度量(doubling metrics)或放宽代表约束寻突破。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号