h****i
发帖数: 84 | 1 【 以下文字转载自 Science 讨论区 】
【 原文由 Hawaii 所发表 】
这个multiway cut problem有没有O(1)-approximation algorithm??
欧在网上古购了半天，现今最好的也就是O(2-2/k)了，k是它的terminal数。
多谢指点！！ | j******e
发帖数: 64 | 2 so when k = 2, it is O(1) le
【在 h****i 的大作中提到】
: 【 以下文字转载自 Science 讨论区 】
: 【 原文由 Hawaii 所发表 】
: 这个multiway cut problem有没有O(1)-approximation algorithm??
: 欧在网上古购了半天，现今最好的也就是O(2-2/k)了，k是它的terminal数。
: 多谢指点！！
| h****i
发帖数: 84 | 3 but...
i'm a little confused by the O(1)
does that mean it's for all k?
【在 j******e 的大作中提到】
: so when k = 2, it is O(1) le
| y***u
发帖数: 101 | 4 check out http://citeseer.ist.psu.edu/calinescu98improved.html
btw, it does not make sense to say O(2-2/k)-approximation.
it's a (2-2/k)-approximation, or an O(1)-approximation.
【在 j******e 的大作中提到】
: so when k = 2, it is O(1) le
|
|
