TY - JOUR
T1 - The minimum spanning k-core problem with bounded cvar under probabilistic edge failures
AU - Ma, Juan
AU - Pajouh, Foad Mahdavi
AU - Balasundaram, Balabhaskar
AU - Boginski, Vladimir
N1 - Publisher Copyright:
© 2016 INFORMS.
PY - 2016/3/1
Y1 - 2016/3/1
N2 - This article introduces the minimum spanning k-core problem that seeks to find a spanning subgraph with a minimum degree of at least k (also known as a k-core) that minimizes the total cost of the edges in the subgraph. The concept of k-cores was introduced in social network analysis to identify denser portions of a social network. We exploit the graph-theoretic properties of this model to introduce a new approach to survivable interhub network design via spanning k-cores; the model preserves connectivity and diameter under limited edge failures. The deterministic version of the problem is polynomial-time solvable due to its equivalence to generalized graph matching. We propose two conditional value-at-risk (CVaR) constrained optimization models t obtain risk-averse solutions for the minimum spanning k-core problem under probabilistic edge failures. We present polyhedral reformulations of the convex piecewise linear loss functions used in these models that enable Benders-like decomposition approaches. A decomposition and branch-and-cut approach is then developed to solve the scenario-based approximation of the CVaR-constrained minimum spanning k-core problem for the aforementioned loss functions. The computational performance of the algorithm is investigated via numerical experiments.
AB - This article introduces the minimum spanning k-core problem that seeks to find a spanning subgraph with a minimum degree of at least k (also known as a k-core) that minimizes the total cost of the edges in the subgraph. The concept of k-cores was introduced in social network analysis to identify denser portions of a social network. We exploit the graph-theoretic properties of this model to introduce a new approach to survivable interhub network design via spanning k-cores; the model preserves connectivity and diameter under limited edge failures. The deterministic version of the problem is polynomial-time solvable due to its equivalence to generalized graph matching. We propose two conditional value-at-risk (CVaR) constrained optimization models t obtain risk-averse solutions for the minimum spanning k-core problem under probabilistic edge failures. We present polyhedral reformulations of the convex piecewise linear loss functions used in these models that enable Benders-like decomposition approaches. A decomposition and branch-and-cut approach is then developed to solve the scenario-based approximation of the CVaR-constrained minimum spanning k-core problem for the aforementioned loss functions. The computational performance of the algorithm is investigated via numerical experiments.
KW - Conditional value-at-risk history
KW - Hop constraints
KW - Minimum spanning k-core
KW - Survivable network design
UR - http://www.scopus.com/inward/record.url?scp=84969922985&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84969922985&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2015.0679
DO - 10.1287/ijoc.2015.0679
M3 - Article
AN - SCOPUS:84969922985
SN - 1091-9856
VL - 28
SP - 295
EP - 307
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 2
ER -