Name
Title | ||
|---|---|---|
A simple greedy approximation algorithm for the minimum connected $$k$$k-Center problem |
Abstract | ||
|---|---|---|
AbstractIn this paper, we consider the connected $$k$$k-Center ($$CkC$$CkC) problem, which can be seen as the classic $$k$$k-Center problem with the constraint of internal connectedness, i.e., two nodes in a cluster are required to be connected by an internal path in the same cluster. $$CkC$$CkC was first introduced by Ge et al. (ACM Trans Knowl Discov Data 2:7, 2008), in which they showed the $$NP$$NP-completeness for this problem and claimed a polynomial time approximation algorithm for it. However, the running time of their algorithm might not be polynomial, as one key step of their algorithm involves the computation of an $$NP$$NP-hard problem. We first present a simple polynomial time greedy-based $$2$$2-approximation algorithm for the relaxation of $$CkC$$CkC--the $$CkC^*$$CkC . Further, we give a $$6$$6-approximation algorithm for $$CkC$$CkC. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10878-015-9831-8 | Periodicals |
Keywords | Field | DocType |
k-Center,Greedy algorithm,Approximation algorithm | Algorithmics,Suurballe's algorithm,Kruskal's algorithm,Minimum k-cut,Discrete mathematics,Combinatorics,Mathematical optimization,Dinic's algorithm,Nondeterministic algorithm,Out-of-kilter algorithm,Algorithm,Greedy algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 4 | 1382-6905 |
Citations | PageRank | References |
3 | 0.40 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dongyue Liang | 1 | 3 | 0.40 |
| Mei Liquan | 2 | 85 | 22.59 |
| James K. Willson | 3 | 6 | 1.49 |
| Wei Wang | 4 | 81 | 12.64 |