Advertisement
Published in:
2013 | OriginalPaper | Chapter
Minimum-Risk Maximum Clique Problem
Authors : Maciej Rysz, Pavlo A. Krokhmal, Eduardo L. Pasiliao
Published in: Dynamics of Information Systems: Algorithmic Approaches
Publisher: Springer New York
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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.