近似(4)

やっぱりVazirani本。
５章のk-center問題を勉強中。
詳細はMetric k-center - Wikipedia。
ちなみに、distanceがmerticでないとすると、P=NPでない限り、
計算可能関数f(n)において、近似率f(n)以内を達成できないことが知られている。

ある証明がよくわかんなくて、はまっている。
「Aが成り立つので、Bとなる。よってCとなる」という文があるのだが、
BからCにどうもたどり着けない。