多樣性公平k-中位問題的(1+ε)-近似算法

摘要： 多樣性公平k-中位問題在數據摘要等對聚類中心選取方式的公平性要求較高的聚類應用領域發揮重要作用.給定一個用戶集合、?個設施集合以及正整數k,該問題的目標是在每個設施集合中開設一個規模受限的子集,使得開設設施數量不超過k,且每個用戶與距離最近的開設設施之間具有較高的相似度.本文將多樣性公平k-中位問題實例映射為低維空間中的小規模實例,并圍繞實例中的點劃分空間以估計最優解中開設設施... （共14頁）