{"id":25125,"date":"2017-10-15T14:36:57","date_gmt":"2017-10-15T09:06:57","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25125"},"modified":"2017-10-15T14:36:57","modified_gmt":"2017-10-15T09:06:57","slug":"k-centers-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/k-centers-problem\/","title":{"rendered":"K Centers Problem"},"content":{"rendered":"

Given n cities and distances between every pair of cities, select k cities to place warehouses (or ATMs or Cloud Server) such that the maximum distance of a city to a warehouse (or ATM or Cloud Server) is minimized.<\/span><\/p>\n

For 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

\"K<\/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

The following diagram taken from here <\/a>illustrates above algorithm.<\/p>\n

\"K<\/p>\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 Algorithm – Given n cities and distances between every pair of cities, select k cities to place warehouses ( ATM or Cloud Server)such that the maximum distance of a city to a warehouse is minimized.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,70144],"tags":[70054,71598,71589,71582,71597,71560,71569,71552,71548,71573,71602,71584,71555,71576,71578,71600,71593,71591,71579,71556,71592,71581,71587,71596,71583,71574,71599,71588,71568,71604,71553,71550,71551,71495,70152,71564,71562,71575,71603,71436,71469,71571,71566,71601,71595,70133,71456,71570,70672,71565,71585,70623,71549,71563,71561,71586,71567,71557,71605,71558,71554,71577,71572,71580,71590,71559,71594,70642],"class_list":["post-25125","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-greedy-algorithm","tag-algorithm","tag-analysis-of-relationships","tag-as-best-as-possible","tag-atm-c-program-source-code","tag-atm-problem-statement","tag-atm-problems","tag-attribute-data","tag-capacitation","tag-cluster-analysis","tag-cluster-analysis-data","tag-cluster-analysis-data-mining","tag-cluster-analysis-for-market-segmentation","tag-cluster-analysis-in-data-mining","tag-cluster-analysis-in-data-mining-notes","tag-cluster-analysis-in-data-mining-pdf","tag-cluster-analysis-in-r-pdf","tag-cluster-analysis-introduction","tag-cluster-analysis-machine-learning","tag-cluster-analysis-marketing","tag-cluster-analysis-pdf","tag-cluster-analysis-types","tag-cluster-data-analysis","tag-clustering-in-image-processing-ppt","tag-clustering-problem-example","tag-data-k","tag-data-mining-cluster-analysis","tag-data-set-with-outliers","tag-data-types-in-cluster-analysis","tag-ddtank","tag-distributed-data-clustering","tag-dominis","tag-et-al-meaning","tag-gon","tag-greedy-algorithm-example","tag-greedy-algorithm-tutorial","tag-gurobi","tag-image-processing-ppt","tag-introduction-to-cluster-analysis","tag-islog","tag-job-scheduling-algorithm","tag-job-scheduling-problem-example","tag-joint-relationship","tag-k-means-clustering-in-r","tag-k-means-clustering-pdf","tag-letters-and-sciences-umd","tag-logn","tag-lpt-jobs","tag-lpt-m","tag-makespan","tag-mapreduce-algorithm","tag-mapreduce-clustering-algorithm","tag-np-hard","tag-np-meaning","tag-optimal-solution-definition","tag-outliers-pdf","tag-parameterized-algorithms","tag-ppt-means","tag-problem-solving-techniques-pdf","tag-set-cover-vertex-cover","tag-types-of-cluster-analysis","tag-types-of-data-in-cluster-analysis","tag-types-of-data-in-cluster-analysis-in-data-mining","tag-types-of-data-in-cluster-analysis-in-data-mining-pdf","tag-what-does-planar-mean","tag-what-is-a-cluster-analysis","tag-what-is-cluster-analysis","tag-what-is-cluster-analysis-in-data-mining","tag-what-is-np-hard"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25125","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=25125"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25125\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25125"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25125"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25125"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}