The minimum spanning k-core problem with bounded cvar under probabilistic edge failures

Juan Ma, Foad Mahdavi Pajouh, Balabhaskar Balasundaram, Vladimir Boginski

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)295-307
Number of pages13
JournalINFORMS Journal on Computing
Volume28
Issue number2
DOIs
StatePublished - 1 Mar 2016

Keywords

  • Conditional value-at-risk history
  • Hop constraints
  • Minimum spanning k-core
  • Survivable network design

Fingerprint

Dive into the research topics of 'The minimum spanning k-core problem with bounded cvar under probabilistic edge failures'. Together they form a unique fingerprint.

Cite this