Metric k-center
Encyclopedia
In graph theory
, the metric k-center, is a combinatorial optimization
problem studied in theoretical computer science
. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the distance of the farthest city from its closest warehouse. In graph theory this means finding a set of k vertices for which the largest distance of any point to its closest vertex in the k-set is minimum. The vertices must be in a metric space, or in other words a complete graph
that satisfies the triangle inequality
.
of size at most k. Dominating set is NP-complete
and therefore the k-center problem is also NP-complete.
approximation algorithm
that achieves an approximation factor of 2 builds S in k iterations. The first iteration chooses an arbitrary vertex and adds it to S. Each subsequent iteration chooses a vertex v for which d(S, v) is maximized and adds v to S. The running time of the algorithm is O(nk).
Another algorithm with the same approximation factor takes advantage of the fact that the k-center problem is equivalent to finding the smallest index i such that Gi has a dominating set of size at most k and computes a maximal independent set
on the of Gi, looking for the smallest index i that has a maximal independent set with a size of at least k.
It is not possible to find an approximation algorithm with an approximation factor of 2 − ε for any ε > 0. Furthermore, the distances of all edges in G must satisfy the triangle inequality if the k-center problem is to be approximated unless P = NP.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the metric k-center, is a combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problem studied in theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the distance of the farthest city from its closest warehouse. In graph theory this means finding a set of k vertices for which the largest distance of any point to its closest vertex in the k-set is minimum. The vertices must be in a metric space, or in other words a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
that satisfies the triangle inequality
Triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side ....
.
Formal definition
Given a complete undirected graph G = (V, E) with distances d(vi, vj) ∈ N satisfying the triangle inequality, find a subset S ⊆ V with |S| = k while minimizing:
Computational complexity
If we sort the edges in nondecreasing order of the distances: d(e1) ≤ d(e2) ≤ … ≤ d(em) and let Gi = (Vi, Ei), where Ei = {e1, e2, …, ei}. The k-center problem is equivalent to finding the smallest index i such that Gi has a dominating setDominating set
In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...
of size at most k. Dominating set is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
and therefore the k-center problem is also NP-complete.
Approximations
A simple greedyGreedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
that achieves an approximation factor of 2 builds S in k iterations. The first iteration chooses an arbitrary vertex and adds it to S. Each subsequent iteration chooses a vertex v for which d(S, v) is maximized and adds v to S. The running time of the algorithm is O(nk).
Another algorithm with the same approximation factor takes advantage of the fact that the k-center problem is equivalent to finding the smallest index i such that Gi has a dominating set of size at most k and computes a maximal independent set
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
on the of Gi, looking for the smallest index i that has a maximal independent set with a size of at least k.
It is not possible to find an approximation algorithm with an approximation factor of 2 − ε for any ε > 0. Furthermore, the distances of all edges in G must satisfy the triangle inequality if the k-center problem is to be approximated unless P = NP.
See also
- Traveling salesman problem
- Minimum k-cutMinimum k-cutIn mathematics, the minimum k-cut, is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut...
- Dominating setDominating setIn graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...
- Independent set (graph theory)Independent set (graph theory)In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...