Combinatorics 3
Metric $k$-center
General $k$-center problem statement: Let \((X, d)\) be a metric space where \(X\) is a set and \(d\) is a metric. A set \(V \subseteq X\) is provided together with a parameter \(k\). The goal is to find a subset \(C \subseteq V\) with \(|C| = k\) such that the maximum distance of a point in \(V\) to the closest point in \(C\) is minimized. The problem can be formally defined as follows: Input: a set $V \subseteq X$, and a parameter $k$. Output: a set $C \subseteq V$ of $k$ points. Goal: Minimize the cost $r^C(V) = \max_{v \in V} d(v, C)$ The k-Center Clustering problem can also be defined on a complete undirected graph $G = (V, E)$ as follows:
Mathematics - Combinatorics
Related fields: Combinatorial optimization Coding theory Discrete and computational geometry Combinatorics and dynamical systems Combinatorics and physics
List of Selected Papers on Algorithms for Large-Scale Graph Processing.
1/ [ISAAC'11] Goodrich, M. T., Sitchinava, N., & Zhang, Q. (2011, December). Sorting, searching, and simulation in the mapreduce framework. In International Symposium on Algorithms and Computation (pp. 374-383). Springer, Berlin, Heidelberg. 1 2 3 4 5 6 7 8 @inproceedings{goodrich2011sorting, title={Sorting, searching, and simulation in the mapreduce framework}, author={Goodrich, Michael T and Sitchinava, Nodari and Zhang, Qin}, booktitle={International Symposium on Algorithms and Computation}, pages={374--383}, year={2011}, organization={Springer} } 2/ [STOC'14] Andoni, A., Nikolov, A., Onak, K., & Yaroslavtsev, G. (2014, May). Parallel algorithms for geometric graph problems. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing (pp. 574-583).