Cardinality of Upper Average and Its Application to Network Optimization
提出一种新特征CUA，用于计数数据集中超过阈值的大值数量，并评估其整体大小，具有连续性和可优化性，应用于网络优化中最小化过载节点或边的数量。
We propose a new characteristic for counting the number of large outcomes in a data set that are considered to be large with respect to some fixed threshold $x$. A popular characteristic used for this purpose is the Cardinality of Upper Tail (${CUT}$), which counts the number of outcomes with magnitude larger than the threshold. We propose a similar characteristic called the Cardinality of Upper Average (${CUA}$), defined as the number of largest data points which have average value equal to the threshold. CUA not only assesses the number of outcomes that are large, but also their overall magnitude. CUA also has superior mathematical properties: it is a continuous function of the threshold, its reciprocal is piecewise linear with respect to threshold, and it is directly optimizable via convex and linear programming. This is in contrast to ${CUT}$, which does not asses the severity of large outcomes, is discontinuous as a function of threshold, and is such that direct optimization yields numerically difficult nonconvex problems. We show that ${CUA}$ can be used to formulate meaningful optimization problems containing counters of the largest components of a vector without introduction of binary variables, leading to large improvement in computation speeds. In particular, we apply the ${CUA}$ concept to create new formulations of network optimization problems involving overloaded nodes or edges, where we aim to minimize the number of most burdened nodes or edges.