China
Africa
Explore chapters and articles related to this topic
1
Published in Ervin Sejdić, Tiago H. Falk, Signal Processing and Machine Learning for Biomedical Big Data, 2018
Mohammad Moghadamfalahi, Murat Akcakaya, Deniz Erdogmus
In particular, one can use a greedy forward algorithm to find a solution within a guaranteed bound around the global optimum when the objective is a monotone submodular set function [14]. To provide the proof, first we need to define monotone set functions.
Selecting energy efficient inputs using graph structure
Published in International Journal of Control, 2023
Isaac Klickstein, Francesco Sorrentino
The set of all control manoeuvres capable of being performed with E units of energy forms a p-dimensional ellipsoid. The volume of the ellipsoid in Equation (13) is known to be related to the determinant of the matrix . The logarithm is taken of the volume as the determinant of the controllability Gramian can fall below the accuracy of double precision floating points values (Sun & Motter, 2013). In Summers et al. (2016), the energy metric in Equation (14) is shown to be a submodular set function. The submodular property of Equation (14) has not been directly applied to the target control problem (only the subproblem when p = n). Nonetheless, when p<n, the submodularity of the log-volume holds (Summers et al., 2016) so we may use a greedy algorithm which retains the same approximation guarantee. For the metric to be minimised, we use the following inverse volume function. Decreasing means the set of reachable states, or control manoeuvres, is larger.
Signed ring families and signed posets
Published in Optimization Methods and Software, 2021
Kazutoshi Ando, Satoru Fujishige
The one-to-one correspondence between finite distributive lattices and finite partially ordered sets (posets) is a well-known theorem of G. Birkhoff (see [5,6]). This implies a nice representation of any distributive lattice by its corresponding poset, where the size of the former (distributive lattice) is often exponential in the size of the underlying set of the latter (poset). A lot of engineering and economic applications bring us distributive lattices as a ring family of sets which is closed with respect to the two binary operations of set union and intersection. Typically we have such a ring family of sets as a family of minimizers of a submodular set function (see [11]). When it comes to a ring family of sets, the underlying set is partitioned into subsets (or components) and we have a poset structure on the partition. This decomposition with a poset structure on the set of components plays important and crucial roles in many practical problems related, for example, to the decomposition of a directed graph into strongly connected components, the Dulmage-Mendelsohn decomposition of a bipartite graph [29], etc. This is a set-theoretical variant of the original Birkhoff theorem, to be called the Birkhoff-Iri decomposition, revealing the correspondence between finite ring families and finite posets on partitions of the underlying sets, which was intensively pursued by Masao Iri around 1978, especially concerned with the problem of what is called the principal partition of discrete systems [13,22–25,28].
A budgeted maximum multiple coverage model for cybersecurity planning and management
Published in IISE Transactions, 2019
Kaiyue Zheng, Laura A. Albert, James R. Luedtke, Eli Towle
Without loss of generality, we assume We also assume If not, the k-cardinality constraint is redundant. kEMMCG formulation (11) maximizes a nondecreasing submodular set function subject to a uniform matroid constraint and a partition matroid constraint, the combination of which is equivalent to a truncated partition matroid constraint. A truncated partition matroid is a matroid. Fisher et al. (1978) demonstrate that a greedy heuristic achieves a 1/2-approximation ratio for maximizing a monotone submodular set function subject to a matroid constraint. Chekuri and Kumar (2004) present a greedy heuristic with a 1/2-approximation ratio for solving the maximum coverage problem subject to a cardinality constraint and group cardinality constraints (a special case of kEMMCG). Their analysis is based on the multiple knapsack problem. Using a similar analysis, we show that the greedy heuristic of Chekuri and Kumar (2004) can be adapted to the general monotone submodular maximization problem subject to a cardinality constraint and group cardinality constraints, of which kEMMCG is an instance. The adapted algorithm achieves the same approximation ratio of 1/2.