Back to Search
Start Over
MAXIMIZING CONVERGENCE TIME IN NETWORK AVERAGING DYNAMICS SUBJECT TO EDGE REMOVAL.
- Source :
-
SIAM Journal on Optimization . 2022, Vol. 32 Issue 4, p2718-2744. 27p. - Publication Year :
- 2022
-
Abstract
- We consider the consensus interdiction problem (CIP), in which the goal is to maximize the convergence time of consensus averaging dynamics subject to removing a limited number of network edges. We first show that CIP can be cast as an effective resistance interdiction problem (ERIP), in which the goal is to remove a limited number of network edges to maximize the effective resistance between a source node and a sink node. We show that ERIP is strongly NP-hard, even for bipartite graphs of diameter three with fixed source/sink edges, and establish the same hardness result for the CIP. We then show that both ERIP and CIP cannot be approximated up to a (nearly) polynomial factor assuming the exponential time hypothesis. Subsequently, we devise a polynomialtime mn-approximation algorithm for the ERIP that only depends on the number of nodes n and the number of edges m but is independent of the size of edge resistances. Finally, using a quadratic program formulation for the CIP, we devise an iterative approximation algorithm to find a first-order stationary solution for the CIP and evaluate its good performance through numerical experiments. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 32
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 161593492
- Full Text :
- https://doi.org/10.1137/21M1458867