Given oracle access to an n-point metric space (M, d), let METRIC 1-MEDIAN be the problem of finding argmin(x is an element of M) Sigma(y is an element of M) d(x, y), breaking ties arbitrarily. We show that METRIC 1-M...
详细信息
Given oracle access to an n-point metric space (M, d), let METRIC 1-MEDIAN be the problem of finding argmin(x is an element of M) Sigma(y is an element of M) d(x, y), breaking ties arbitrarily. We show that METRIC 1-MEDIAN has a deterministic nonadaptive O(n(3/2))-time 4-approximation algorithm. (c) 2013 Elsevier B.V. All rights reserved.
暂无评论