著者

畑野 航琉 中野 眞一

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 A (ISSN:09135707)

巻号頁・発行日

vol.J106-A, no.1, pp.1-4, 2023-01-01

---

顧客の集合C,施設の集合F,各施設f ∈ Fの開設コストop(f),各顧客c ∈ Cの各施設f ∈ Fへの接続コストco(c, f)があたえられたとき,幾つかの施設を開設し,各顧客を開設施設に割り当て,かつ,各開設施設にr人以上の顧客を割り当てるようにしたい.このとき,全ての開設コストと全ての接続コストの合計が最小の解を計算する問題をmin-sum r-gathering問題という.本論文では,開設コストが0であり,接続コストが三角不等式を満たすとき,各顧客を最も近い開設施設に割り当てるという条件を追加したmin-sum r-gathering問題,すなわち近接条件付きのmin-sum r-gathering問題を解く,近似比3rの近似解を計算する多項式時間アルゴリズムをあたえる.このアルゴリズムは,rが定数のときこの問題を解く初の定数倍近似アルゴリズムである.