Abstract:We consider cardinality-constrained optimization of set functions over the nodes of a graph. The standard greedy algorithm selects each node according to its immediate marginal contribution, a local criterion that may fail to anticipate the synergies within the final set. We introduce past-aware game-theoretic centrality (PAGTC), which evaluates a candidate node through its expected marginal contribution over the possible completions of the current partial solution to the prescribed target size. This yields a sequential selection strategy that explicitly accounts for the final budget. For nonnegative monotone submodular objectives and a budget $r$, we prove an approximation guarantee of $r/(2r-1)$ and derive computable a posteriori bounds. Since direct PAGTC evaluation involves averaging over a large number of coalitions, we extend an exact computation framework for game-theoretic centrality and derive efficiently computable expressions for two classes of graph-optimization problems, namely facility location and influence in complex contagion, covering both submodular and non-submodular cases. The numerical results show that the benefits depend on the objective and are most pronounced for complex contagion, where submodularity does not hold.
From: Francesco Zigliotto [view email]
[v1]
Mon, 10 Nov 2025 14:48:40 UTC (272 KB)
[v2]
Mon, 1 Dec 2025 15:04:49 UTC (272 KB)
[v3]
Tue, 8 Sep 2026 10:36:51 UTC (370 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。