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

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