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

CREATORChristian Schulz, Jakob Ternes, Henning Woydt
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70067
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.25642

Browse the full library · About the Tower of Babel