Advances in Exact and Approximate Group Closeness Centrality Maximization
Christian Schulz, Jakob Ternes, Henning Woydt · 2026
Read Advances in Exact and Approximate Group Closeness Centrality Maximization by Christian Schulz, Jakob Ternes, Henning Woydt (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-25642.txt.
Description
Schulz, Ternes, and Woydt improve algorithms for group closeness centrality maximization. The task is to pick k vertices in a graph that minimize total distance to all others. It is NP-hard. The best exact method solves integer programs of growing size. The authors add a data reduction rule that removes variables with provably fixed distances. They also seed the solver with an approximate solution. They report speedups of 4.5 times over the prior exact method. They also prove the common greedy method can be arbitrarily poor.
Catalog record
| CREATOR | Christian Schulz, Jakob Ternes, Henning Woydt |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70067 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.25642