TY - JOUR

T1 - Minimum-Risk Maximum Clique Problem

AU - Rysz, Maciej

AU - Krokhmal, Pavlo A.

AU - Pasiliao, Eduardo L.

PY - 2013

Y1 - 2013

N2 - In this work, we consider the minimum-risk maximum clique problem on stochastic graphs. Namely, assuming that each vertex of the graph is associated with a random variable describing a cost or a loss, such that the joint distribution of all variables on the graph is known, the goal is to determine a clique in the graph that has the lowest risk, given a specific risk measure. It is shown that in the developed problem formulation, minimization of risk is facilitated through inclusion of additional vertices in the partial solution, whereby an optimal solution represents a maximal clique in the graph. In particular, two instances of risk-averse maximum clique problems are considered, where risk exposures of a graph's vertices are "isolated" (i.e., not dependent on risk profiles of other vertices) and "neighbor-dependent," or dependent on the risk profiles of adjacent vertices. Numerical experiments on randomly generated Erdos-Renyi demonstrating properties of optimal risk-averse maximum cliques are conducted.

AB - In this work, we consider the minimum-risk maximum clique problem on stochastic graphs. Namely, assuming that each vertex of the graph is associated with a random variable describing a cost or a loss, such that the joint distribution of all variables on the graph is known, the goal is to determine a clique in the graph that has the lowest risk, given a specific risk measure. It is shown that in the developed problem formulation, minimization of risk is facilitated through inclusion of additional vertices in the partial solution, whereby an optimal solution represents a maximal clique in the graph. In particular, two instances of risk-averse maximum clique problems are considered, where risk exposures of a graph's vertices are "isolated" (i.e., not dependent on risk profiles of other vertices) and "neighbor-dependent," or dependent on the risk profiles of adjacent vertices. Numerical experiments on randomly generated Erdos-Renyi demonstrating properties of optimal risk-averse maximum cliques are conducted.

KW - Coherent risk measures

KW - Conditional value-at-risk

KW - Maximum clique problem

KW - Stochastic graphs

UR - http://www.scopus.com/inward/record.url?scp=84892757818&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84892757818&partnerID=8YFLogxK

U2 - 10.1007/978-1-4614-7582-8_8

DO - 10.1007/978-1-4614-7582-8_8

M3 - Article

AN - SCOPUS:84892757818

SN - 2194-1009

VL - 51

SP - 251

EP - 267

JO - Springer Proceedings in Mathematics and Statistics

JF - Springer Proceedings in Mathematics and Statistics

ER -