最小負載受限k-中位問題的近似方案

摘要： 給定度量空間中的用戶集合C和帶有最小負載τ:F→(0,|C|]的設(shè)施集合F以及正整數(shù)k,最小負載受限k-中位問題的一個可行解(H,σ)由滿足|H|≤k的開設(shè)設(shè)施集合H?F和滿足|σ^-1(f)|≥τ(f)?f∈H的映射σ:C→H組成.(H,σ)的費用為∑_(c∈C)δ(c,σ(c)),其中,δ(c,σ(c))為c與σ(c)之間的距離.最小負載受限k-中位問題的目標是找到費用... （共20頁）