Min-sum controllable risk problems with concave risk functions of the same value range

Abstract

A min-sum controllable risk problem, defined on a given set of elements or on combinatorial structures, which are either paths of a directed acyclic graph or spanning trees of an undirected graph, with resource-dependent risk functions of the elements, is studied. The resource amount is limited, and the objective is to distribute it between the selected elements or elements of the selected structure so that the total risk is minimized. A reduction to a series of easier problems is suggested. Solution approaches based on this reduction are asymptotically faster than the solution approaches suggested in the literature for special cases of this problem.