This content originally appeared on HackerNoon and was authored by Computational Technology for All
:::info Authors:
(1) Junwei Su, Department of Computer Science, the University of Hong Kong and jwsu@cs.hku.hk;
(2) Chuan Wu, Department of Computer Science, the University of Hong Kong and cwu@cs.hku.hk.
:::
Table of Links
5 A Case Study on Shortest-Path Distance
6 Conclusion and Discussion, and References
9 Procedure for Solving Eq. (6)
10 Additional Experiments Details and Results
11 Other Potential Applications
9 Procedure for Solving Eq. (6)
First recall that the optimization problem we want to solve is as follows.
\
\ where k is the given initial set size and Ds(.) is given in Def. 2 with shortest path distance as the metric. Eq. 6 amounts to the well-known k-center problem [14] in graph theory and is NP-hard. For our experiment, we use Eq. 6 as guidance and modify the simple greedy algorithm, farthest-first traversal, to be a sampling method for obtaining a solution. We now describe how we modified the standard greedy algorithm into a sampling algorithm. We start with describing the standard greedy algorithm.
\
\ The procedure described above is a standard 2-approximation greedy algorithm for k-center problem. Next, we describe its sampling variant which use the distance as the chance of being sampled.
9.1 Running Time Complexity
It is obvious that the procedure above runs in O(k) if the distance between any pair of vertices is given and runs in O(kn) if the distance needed to be computed for each step, where n is the number of vertice.
\
:::info This paper is available on arxiv under CC BY 4.0 DEED license.
:::
\
This content originally appeared on HackerNoon and was authored by Computational Technology for All
Computational Technology for All | Sciencx (2024-10-22T08:00:18+00:00) Optimizing GNNs: A Sampling-Based Solution to the k-Center Problem. Retrieved from https://www.scien.cx/2024/10/22/optimizing-gnns-a-sampling-based-solution-to-the-k-center-problem/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.