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

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