Worst-case and Probabilistic Analysis of a Geometric Location Problem
We consider the problem of choosing K "medians" among n points on the Euclidean plane such that the sum of the distances from each of the n points to its closest median is minimized. We show that this problem is NP-complete. We also present two heuristics that produce arbitrarily good solu...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148980 |
| _version_ | 1826197930918281216 |
|---|---|
| author | Papadimitriou, Christos H. |
| author_facet | Papadimitriou, Christos H. |
| author_sort | Papadimitriou, Christos H. |
| collection | MIT |
| description | We consider the problem of choosing K "medians" among n points on the Euclidean plane such that the sum of the distances from each of the n points to its closest median is minimized. We show that this problem is NP-complete. We also present two heuristics that produce arbitrarily good solutions with probability going to 1. One is a partition heuristic, and works when K grows lineraly -- or almost so -- with n. The other is the "honeycomb" heuristic, and is applicable to rates of grother of K of the form K ~ n^Є, 0<Є<1. |
| first_indexed | 2024-09-23T10:55:58Z |
| id | mit-1721.1/148980 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:55:58Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489802023-03-30T03:57:57Z Worst-case and Probabilistic Analysis of a Geometric Location Problem Papadimitriou, Christos H. We consider the problem of choosing K "medians" among n points on the Euclidean plane such that the sum of the distances from each of the n points to its closest median is minimized. We show that this problem is NP-complete. We also present two heuristics that produce arbitrarily good solutions with probability going to 1. One is a partition heuristic, and works when K grows lineraly -- or almost so -- with n. The other is the "honeycomb" heuristic, and is applicable to rates of grother of K of the form K ~ n^Є, 0<Є<1. 2023-03-29T14:15:46Z 2023-03-29T14:15:46Z 1980-02 https://hdl.handle.net/1721.1/148980 6697158 MIT-LCS-TM-153 application/pdf |
| spellingShingle | Papadimitriou, Christos H. Worst-case and Probabilistic Analysis of a Geometric Location Problem |
| title | Worst-case and Probabilistic Analysis of a Geometric Location Problem |
| title_full | Worst-case and Probabilistic Analysis of a Geometric Location Problem |
| title_fullStr | Worst-case and Probabilistic Analysis of a Geometric Location Problem |
| title_full_unstemmed | Worst-case and Probabilistic Analysis of a Geometric Location Problem |
| title_short | Worst-case and Probabilistic Analysis of a Geometric Location Problem |
| title_sort | worst case and probabilistic analysis of a geometric location problem |
| url | https://hdl.handle.net/1721.1/148980 |
| work_keys_str_mv | AT papadimitriouchristosh worstcaseandprobabilisticanalysisofageometriclocationproblem |