やっぱりVazirani本。 5章のk-center問題を勉強中。 詳細はMetric k-center - Wikipedia。 ちなみに、distanceがmerticでないとすると、P=NPでない限り、 計算可能関数f(n)において、近似率f(n)以内を達成できないことが知られている。ある証明がよくわかん…
初Acceptキタッ!!
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。