Cardinality of upper average and its application to network optimization
MetadataShow full item record
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.
The article of record as published may be found at http://dx.doi.org/10.1137/16M1095913
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
El Khoury, Jihad A.; Lapp, Andres (Monterey, CA; Naval Postgraduate School, 2018);In the literature on asymmetric warfare, a great deal of disagreement and contradictory theories have arisen concerning factors affecting the outcomes of war. In an attempt to resolve the discrepancies among these theories, ...
Banschbach, David C. (Monterey, California. Naval Postgraduate School, 2008);When implementing a system of sensors, one of the biggest challenges is to establish a threshold at which a signal is generated. All signals that exceed this detection threshold are then investigated to determine whether ...
Nielson, Gregory; Franke, Richard (1997);An algorithm for computing a triangulated surface which separates a collection of data points that have been segmented into a number of different classes is presented. The problem generalizes the concept of an isosurface ...