{"id":26544,"date":"2017-12-20T21:36:37","date_gmt":"2017-12-20T16:06:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26544"},"modified":"2017-12-20T21:36:37","modified_gmt":"2017-12-20T16:06:37","slug":"k-centers-problem-greedy-approximate-algorithm","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/k-centers-problem-greedy-approximate-algorithm\/","title":{"rendered":"K Centers Problem | Set 1 (Greedy Approximate Algorithm)"},"content":{"rendered":"

K Centers Problem | Set 1 (Greedy Approximate Algorithm) – learn in 30 sec from microsoft awarded MVPFor example consider the following four cities, 0, 1, 2 and 3 and distances between them, how do place 2 ATMs among these 4 cities so that the maximum distance of a city to an ATM is minimized.<\/p>\n

There is no polynomial time solution available for this problem as the problem is a known NP-Hard problem. There is a polynomial time Greedy approximate algorithm, the greedy algorithm provides a solution which is never worse that twice the optimal solution. The greedy solution works only if the distances between cities follow Triangular Inequality<\/a> (Distance between two points is always smaller than sum of distances through a third point).<\/p>\n[ad type=”banner”]\n

The 2-Approximate Greedy Algorithm:<\/strong>
\n1) Choose the first center arbitrarily.<\/p>\n

2) Choose remaining k-1 centers using the following criteria.
\nLet c1, c2, c3, \u2026 ci be the already chosen centers. Choose
\n(i+1)\u2019th center by picking the city which is farthest from already
\nselected centers, i.e, the point p which has following value as maximum
\nMin[dist(p, c1), dist(p, c2), dist(p, c3), \u2026. dist(p, ci)]\n

Example (k = 3 in the above shown Graph)<\/strong>
\na) Let the first arbitrarily picked vertex be 0.<\/p>\n

b) The next vertex is 1 because 1 is the farthest vertex from 0.<\/p>\n

c) Remaining cities are 2 and 3. Calculate their distances from already selected centers (0 and 1). The greedy algorithm basically calculates following values.<\/p>\n

Minimum of all distanced from 2 to already considered centers
\nMin[dist(2, 0), dist(2, 1)] = Min[7, 8] = 7<\/p>\n

Minimum of all distanced from 3 to already considered centers
\nMin[dist(3, 0), dist(3, 1)] = Min[6, 5] = 5<\/p>\n

After computing the above values, the city 2 is picked as the value corresponding to 2 is maximum.<\/p>\n

Note that the greedy algorithm doesn\u2019t give best solution for k = 2 as this is just an approximate algorithm with bound as twice of optimal.<\/p>\n[ad type=”banner”]\n

Proof that the above greedy algorithm is 2 approximate.<\/strong>
\nLet OPT be the maximum distance of a city from a center in the Optimal solution. We need to show that the maximum distance obtained from Greedy algorithm is 2*OPT.<\/p>\n

The proof can be done using contradiction.<\/p>\n

a) Assume that the distance from the furthest point to all centers is > 2\u00b7OPT.<\/p>\n

b) This means that distances between all centers are also > 2\u00b7OPT.<\/p>\n

c) We have k + 1 points with distances > 2\u00b7OPT between every pair.<\/p>\n

d) Each point has a center of the optimal solution with distance <= OPT to it.<\/p>\n

e) There exists a pair of points with the same center X in the optimal solution (pigeonhole principle: k optimal centers, k+1 points)<\/p>\n

f) The distance between them is at most 2\u00b7OPT (triangle inequality) which is a contradiction.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"

K Centers Problem – Greedy Approximate Algorithm – Let OPT be the maximum distance of a city from a center in the Optimal solution. We need to show that<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73906,78521],"tags":[79064,83627,83630,83628,79065,79060,79063,79062,79061,83629,79059,83626],"class_list":["post-26544","post","type-post","status-publish","format-standard","hentry","category-graph-algorithms","category-hard-problems","tag-a-best-possible-heuristic-for-the-k-center-problem","tag-clustering-to-minimize-the-maximum-intercluster-distance","tag-design-a-greedy-approximated-algorithm-to-solve-the-k-center-problem","tag-interval-partitioning-geeksforgeeks","tag-k-center-clustering-2-approximation","tag-k-center-clustering-algorithm","tag-k-center-problem-code","tag-k-center-problem-geeksforgeeks","tag-k-center-problem-np-complete","tag-k-centers-problem-set-1-greedy-approximate-algorithm","tag-k-center-approximation","tag-k-center-clustering"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26544","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26544"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26544\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26544"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26544"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26544"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}