## Abstract

In this work, we consider a class of risk-averse maximum weighted subgraph problems (R-MWSP). Namely, assuming that each vertex of the graph is associated with a stochastic weight, such that the joint distribution is known, the goal is to obtain a subgraph of minimum risk satisfying a given hereditary property. We employ a stochastic programming framework that is based on the formalism of modern theory of risk measures in order to find minimum-risk hereditary structures in graphs with stochastic vertex weights. The introduced form of risk function for measuring the risk of subgraphs ensures that optimal solutions of R-MWS problems represent maximal subgraphs. A graph-based branch-and-bound (BnB) algorithm for solving the proposed problems is developed and illustrated on a special case of risk-averse maximum weighted clique problem. Numerical experiments on randomly generated Erdös-Rényi graphs demonstrate the computational performance of the developed BnB.

Original language | English (US) |
---|---|

Pages (from-to) | 167-185 |

Number of pages | 19 |

Journal | Journal of Combinatorial Optimization |

Volume | 28 |

Issue number | 1 |

DOIs | |

State | Published - Jul 2014 |

Externally published | Yes |

## Keywords

- Coherent risk measures
- Maximum weight clique problem
- Risk-averse maximum clique problem
- Risk-averse maximum weighted subgraph problem
- Stochastic weights

## ASJC Scopus subject areas

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics