Search

In this study, we generalize the concept of the k-order additivity of a set function. First, we discuss the Mobius transform for a non-discrete set function. Next, we generalize the definition of the k-order additivity of a set function using the Mobius transform and provide the equivalent conditions for the k-order additivity. Furthermore, we consider the k-order additivity of the distorted monotone measure. We prove that under certain conditions, a distorted measure is k-order additive if and only if the distortion function is a polynomial of k-th order.

We examine sufficient and necessary conditions for the Choquet integral on the support of its integrand to be equal to the integral on a set which includes this support (we consider the problem in the case of a locally compact Hausdorff space).

An echo chamber effect describes the situation in which opinions are amplified by communication and repetition inside a relatively closed social system. In this article, we will detect the echo chamber effect in real-world data set and measure this effect during the information diffusion process. Any user will be influenced by its neighbors or echo chamber effect. Also, we assume that these activation events from each activated neighbor and from echo chamber effect are independent. In this article, we detect and model the echo chamber effect for the first time. Then, the influence maximization with echo chamber (IMEC) problem aims to select $k$ users to propagate information such that the expected number of activated users is maximized. We formulate this problem using a graph model and analyze the NP-hardness. Second, the objective of IMEC as a set function is proved to be neither submodular nor supermodular. Then, an improved greedy algorithm is proposed, which is combined metaheuristic strategies. Finally, experimental results show that our algorithm is effective in detecting echo chamber effect and efficiency in selecting seed nodes.

In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0 , 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1 . For general value of the curvature parameter α ∈ [ 0 , 1 ] , we present an approximation algorithm with a factor of 1 + h α ( y ) + Δ ⋅ [ 3 + α − ( 2 + α ) y − ( 1 + α ) h α ( y ) ] 2 + α + ( 1 + α ) ( 1 − y ) , where y ∈ [ 0 , 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0.5008 when setting y = 0.9 , coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions.

Three stage sixth-order exponentially fitted and trigonometrically fitted explicit two-derivative Runge–Kutta-type methods are proposed for solving $$u^{'''}(t) = \, f(t,u(t),u'(t)).$$ The idea of construction is based on linear composition of the set functions $$e^{\omega t}$$ and $$e^{-\omega t}$$ for exponentially fitted and $$e^{i\omega t}$$ and $$e^{-i\omega t}$$ for trigonometrically fitted with $$\omega \in \mathbb {R}$$ to integrate initial value problems. The selected coefficients of two-derivative Runge–Kutta-type method are modified to depend on the principle frequency of the numerical problems to construct exponentially fitted and trigonometrically fitted Runge–Kutta-type direct methods, denoted as EFTDRKT6 and TFTDRKT6 methods. The numerical experiments illustrate competence of the new exponentially fitted and trigonometrically fitted method compared to existing methods for solving special type third-order ordinary differential equations with initial value problems.

In solving mathematical problems so far, Riemann's integral theory is quite adequate for solving pure mathematics and applications problems. But not all problems can be solved using this integration, such as a discontinuous function that is not Riemann's integration. Lebesgue integral is an integration concept based on measure and can solve finite and unlimited function problems and be solved in a more general set domain. One of the bases of this integration is the Lebesgues measure includes the set of real numbers, where the length of the interval is the endpoints. The alternative use of this integral is widely used in various studies such as partial differential equations, quantum mechanics, and probabilistic analysis, requiring the integration of arbitrary set functions. This paper will show a comprehensive bibliometric survey of peer-reviewed articles referring to Lebesgue measure in integration. Search results are obtained 832 papers in the google scholar database and 997 papers using Lebesgue measure integration in optimization. It can also be seen that the research have 4 clusters and 3 clusters respectively with scattered keywords for each cluster. Finally, using bibliographic data can be obtained Lebesgues measure in integration and optimization supports many of the research and provides productive citations to citing the study.

We investigate a Linear-Quadratic-Gaussian (LQG) control and sensing co-design problem, where one jointly designs sensing and control policies. We focus on the realistic case where the sensing design is selected among a finite set of available sensors, where each sensor is associated with a different cost (e.g., power consumption). We consider two dual problem instances: sensing-constrained LQG control, where one maximizes control performance subject to a sensor cost budget, and minimum-sensing LQG control, where one minimizes sensor cost subject to performance constraints. We prove no polynomial time algorithm guarantees across all problem instances a constant approximation factor from the optimal. Nonetheless, we present the first polynomial time algorithms with per-instance suboptimality guarantees. To this end, we leverage a separation principle, that partially decouples the design of sensing and control. Then, we frame LQG co-design as the optimization of approximately supermodular set functions; we develop novel algorithms to solve the problems; and we prove original results on the performance of the algorithms, and establish connections between their suboptimality and control-theoretic quantities. We conclude the paper by discussing two applications, namely, sensing-constrained formation control and resource-constrained robot navigation., Comment: Accepted to IEEE TAC. Includes contributions to submodular function optimization literature, and extends conference paper arXiv:1709.08826

In the paper, we consider the problem of maximizing the multilinear extension of a nonsubmodular set function subject to a k-cardinality constraint with adaptive rounds of evaluation queries. We devise an algorithm which achieves a ratio of ( 1 − e − γ 2 − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds and O ( n log ⁡ n / ϵ 2 ) queries, where γ is the continuous generic submodularity ratio that compares favorably in flexibility to the traditional submodularity ratio proposed by Das and Kempe. The key idea of our algorithm is originated from the parallel-greedy algorithm proposed by Chekuri et al., but incorporating with two major changes to retain the performance guarantee: First, identify all good coordinates with the continuous generic submodularity ratio and gradient values approximately as large as the best coordinate, and increase along all these coordinates uniformly; Second, increase x along these coordinates by a dynamical increment whose value depends on γ. The key difficulty of our algorithm is that when the function is nonsubmodular, the set of the best coordinate does not decrease during iterations; while provided submodularity, the decreasing can be ensured by the parallel-greedy algorithm. Our algorithms slightly compromise performance guarantee for the sake of extending to constrained nonsubmodular maximization with parallelism, provided that the state-of-art algorithm for the corresponding submodular version attains an approximation ratio of ( 1 − 1 / e − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds.

This paper formalises the operations on capacities in matrix algebra framework. Various quantities that characterise the importance of the inputs and their dependencies are expressed through capacity derivatives, obtained through matrix–vector multiplication. Many relations between the set functions derivatives are established and found to be the consequences of the Divergence Theorem. New formulas for Shapley values and nonmodularity indices are found. The sums of the Shapley interaction indices are found to be related to lower order derivatives at the top and bottom elements of the respective power sets. The presented methods simplify many calculations and will facilitate efficient software implementations and applications of the capacity-based decision making methods.

Using polarity, we give an outer polyhedral approximation for the epigraph of set functions. For a submodular function, we prove that the corresponding polar relaxation is exact; hence, it is equivalent to the Lov\'asz extension. The polar approach provides an alternative proof for the convex hull description of the epigraph of a submodular function. Computational experiments show that the inequalities from outer approximations can be effective as cutting planes for solving submodular as well as non-submodular set function minimization problems.

This article proposes a level set approach to segment images with N regions by using a single level set function. Many works use several level set fronts or hierarchical approach to solve this problem. We propose a general formulation of the level set propagation function based on the knowledge for two regions. A modified likelihood function is proposed, and each background probability is maximized. A single propagation function is achieved from N logarithmic components. Experiments are performed on synthetic images with normal probability and computed tomography images of patients with hemorrhagic stroke. Our approach is compared with other ones known in the literature, and the level set was superior in 10 metrics out of 13 evaluated, with an accuracy of 99.67% and FSIM 93.96%. These results confirm the effectiveness of the proposed method.

Generic submodularity ratio γ is a general measurement to characterize how close a nonnegative monotone set function is to be submodular. In this paper, we make a systematic analysis of greedy algorithms for maximizing a monotone and normalized set function with a generic submodularity ratio γ under Cardinality constraints, Knapsack constraints, Matroid constraints and K-intersection constraints.

In this work, we investigate online bicriteria algorithms that consider both coverage and cost in the team formation problem, which selects a set of experts with the objective of maximizing the difference of two set functions f − l , where function f is non-negative normalized monotone approximately submodular, and function l is non-negative linear. By exploiting the problem's combinatorial structure, we present three bicriteria algorithms along with their corresponding competitive analysis. The first two algorithms handle the cases where function f is γ-weakly submodular, and strictly γ-weakly submodular, respectively. The last algorithm is more general by integrating the first two with extra parameters introduced.

M ♮ -concavity is a key concept in discrete convex analysis. For set functions, the class of M ♮ -concavity is a proper subclass of submodularity. It is a well-known fact that the set of minimizers of a submodular function forms a distributive lattice, where every finite distributive lattice is possible to appear. It is a natural question whether every finite distributive lattice appears as the minimizer set of an M ♮ -concave set function. This paper affirmatively answers the question.

We examine measures on a Banach space E that are invariant under shifts by arbitrary vectors of the space and are additive extensions of a set function defined on the family of bars with converging products of edge lengths that do not satisfy the σ-finiteness condition and, perhaps, the countable additivity condition. We introduce the Hilbert space ℋ of complex-valued functions of the space E of functions that are square integrable with respect to a shift-invariant measure. We analyze properties of semigroups of shift operators in the space ℋ and the corresponding generators and resolvents. We obtain a criterion of the strong continuity of such semigroups. We introduce and examine mathematical expectations of operators of shifts along random vectors by a one-parameter family of Gaussian measures that form a semigroup with respect to the convolution. We prove that the family of mathematical expectations is a one-parameter semigroup of linear self-adjoint contraction mappings of the space ℋ, find invariant subspaces of operators of this semigroup, and obtain conditions of its strong continuity.

We consider embedded Haar type spaces associated with cell subdivisions of a smooth manifold. We use an adaptivity criterion connected with a nonnegative set function possessing certain monotonicity properties. We propose an algorithm for constructing embedded spaces satisfying the adaptivity criterion. To construct the wavelet decomposition, we apply the nonclassical approach and obtain the adaptive wavelet decomposition of the Haar type space on the manifold. Some model examples are given.

It is known that deterministic and probabilistic models of measured quantities, processes and fields, as well as physical and probabilistic measures, make it possible to form a measurement result, to provide it with the properties of objectivity and reliability. On their basis, the measuring instruments necessary for obtaining new knowledge and maintaining the process of technological development of production are being developed and improved. Therefore, the issues of improving and developing models and measures in measurement methodology play an increasingly important role in achieving high measurement accuracy and expanding the areas of their application. The article is devoted to the features and results of the study of the application of models and measures in measurements. It is shown that the physical correctness and the need for setting up measuring experiments, performing tasks and conditions for their implementation, substantiating adequate models and measures significantly affect the obtained measurement result. The features of the modern methodology of using models of signals and fields and measures for evaluating the results of measuring physical quantities, including thermophysical ones, which are represented by random quantities and angles are presented. In the general case, a measure is a countably additive set function that acquires only negative values ​​in any way, including infinity. The use of charge as a mathematical model significantly expands the boundaries of the practical application of the methods of measure theory in metrology. Examples of probabilistic measures on a straight line, on a circle and a charge, as well as physical measures are considered. The concept of coordination of physical and probabilistic measures has been substantiated with the aim of a unified approach to assessing the measurement result. The joint use of physical and probabilistic measures for the formation of a measurement result allows to a certain extent overcome the problem of measurement homomorphism. An example of using a set of physical and probabilistic measures in the hardware and software modules of information and measuring systems is given. The probabilistic normalized measure is a non-physical degree, but a measure of the totality of the action of various random factors on the value and characteristics of data and the result of measurements when they are carried out. The use of a probabilistic measure in the statistical processing of measurement data makes it possible to increase the accuracy of the measurement result compared to the accuracy of the measurement data. The degree of information protection during measurements is complex. The measure is formed by many factors, the action of most of which is of a random nature. This makes it possible to determine such a measure as probabilistic, which can be applied both for individual operations, for example, transmission of measurement data via communication channels, registration of the measurement result, and for the entire measurement process as a whole. The stochastic approach in the theory of measurements is of particular importance in the case of measurements of physical quantities that have a pronounced probabilistic nature, for example, in the case of nano-measurements, the study of quantum effects, and the like. Currently, the use of the SI international system of units at the quantum level and the concept of uncertainty for evaluating measurement results, which are the foundation of measurement practice, requires a wide range of theoretical and simulation studies of measurement processes in various subject areas to form a unified measurement methodology.

Using a short proof, we show that every set function f can be decomposed into the difference of two monotone increasing and strictly submodular functions g and h, i.e., $$f=g-h$$ , and every set function f can also be decomposed into the difference of two monotone increasing and strictly supermodular functions g and h, i.e., $$f=g-h$$ .

We develop a framework for the distributed minimization of submodular functions. Submodular functions are a discrete analog of convex functions and are extensively used in large-scale combinatorial optimization problems. While there has been a significant interest in the distributed formulations of convex optimization problems, distributed minimization of submodular functions has received relatively little research attention. Our framework relies on an equivalent convex reformulation of a submodular minimization problem, which is efficiently computable. We then use this relaxation to exploit methods for the distributed optimization of convex functions. The proposed framework is applicable to submodular set functions as well as to a wider class of submodular functions defined over certain lattices. We also propose an approach for solving distributed motion-planning problems in discrete state space based on submodular function minimization. We establish through a challenging setup of the capture the flag game that submodular functions over lattices can be used to design artificial potential fields for multiagent systems with discrete inputs. These potential fields are designed such that their minima correspond to desired behaviors, that is, agents are attracted toward their goals and are repulsed from obstacles and from each other for collision avoidance. Finally, we demonstrate that the proposed distributed framework can be employed effectively for generating feasible trajectories in such motion coordination problems.

This article presents some properties of real Birkhoff weak integrable functions with respect to a non-additive set function, such as Holder inequality, Minkowski inequality, Lebesgue type convergence theorems and Fatou type theorem.

The paper offers an extension and generalization of the definitions of the weighted arithmetic mean WAM, the ordered weighted averaging function OWA and the discrete Choquet integral using not only...

Any set function can be decomposed into the difference of two monotone nondecreasing submodular functions. This theorem plays an important role in the set function optimization theory. In this paper, we show a variation that any set function can be decomposed into the difference of two monotone nondecreasing supermodular functions. Meanwhile, we give an example in social network optimization and construct algorithmic solutions for the maximization problem of set functions with this variation of DS decomposition.

A cooperative game (N, v) is said to be monotone if $$v(S)\ge v(T)$$ for all $$T\subseteq S\subseteq N$$, and k-monotone for $$k\ge 2$$ if $$v(\cup _{i=1}^k S_i)\ge \sum _{I:\,\emptyset \ne I\subseteq \{1,\ldots , k\}} (-1)^{|I|-1} v(\cap _{i\in I} S_i)$$ for all k subsets $$S_1,\ldots ,S_k$$ of N. Call a set function v totally monotone if it is monotone and k-monotone for all $$k\ge 2$$. To generalize both of marginal contribution and Harsanyi dividend, we define derivatives of v as $$v^{(0)}=v$$ and for pairwise disjoint subsets $$R_1,\dots ,R_k$$ of N, $$v'_{R_1}(S)=v(S\cup R_1)-v(S)$$ for $$S\subseteq N\setminus R_1$$, and $$v^{(k)}_{R1,\dots ,R_k}(S)=(v^{(k-1)}_{R_1,\dots ,R_{k-1}})'_{R_k}(S)$$ for $$S\subseteq N\setminus \cup _{i=1}^k R_i$$. We generalize the equivalence between convexity and monotonicity of marginal contribution of v to total monotonicity and higher derivatives of v from several aspects. We also give the Taylor expansion of any game (set function) v.

© 2019 Elsevier B.V. A new approach to non-additive set functions is presented. The notion of non-additive measure is extended using non-commutative and non-associative operations with two parameters and the cumulative distribution function of a random variable. One new non-additive measure, generalized pseudo-probability measure, is defined and some of its basic properties are proven.

In this paper, we study monotone set functions defined as the composition of an additive measure with a strictly increasing function. This function is a unary operator in continuous-valued logic, called the tau function, and it is a generator function-based parametric mapping. We provide a necessary and sufficient condition for the equality of two tau functions that are induced by different generator functions. Using the tau function and its properties, we introduce a new monotone measure that we call the tau-additive measure. This measure is computationally simple and it can be viewed as an upper or lower probability depending on the parameter settings of the tau function. We present the parameter-dependent submodularity and supermodularity of the tau-additive measure and show how this measure can be constructed from a set function on a finite set. This procedure is analogous to how the well-known lambda-additive measure can be constructed, but our method is computationally simpler. We demonstrate that the tau-additive measure can be used to approximate the lambda-additive measure. Lastly, exploiting these theoretical results, we present an application in the area of human resource management.

At comparison of organizational structure for example frontier subdivisions of the rapid reacting there is a task of estimation of quality of these variants, idest in number to measure absolute or even relative value of efficiency them organizationally-regular structures at implementation of the tasks and functions fixed on subdivision. It is known that the organizationally-regular structure of frontier subdivision it basis of his possibility to execute a task on purpose. At compared different organizational structures that provide implementation of functions of operatively-official (battle) activity there is a task of estimation of their quality. One of indexes of quality there is an index of losses of efficiency of mechanism of realization of functions of guard and defense of state boundary. Without regard to plenty of publications on this subjects, obvious is a fact of that normative index of losses of efficiency of mechanism of realization of functions of guard and defense of state boundary, in the marked sphere of research not examined. The aim of the article are a ground and synthesis of index of losses of efficiency of realization of one function of operatively-official (battle) activity within the limits of organizationally-regular structure. For determination of principle of estimation of index of losses of efficiency in the article one function is considered only for one structure and it is considered that in the organizational structure of frontier subdivision (for example, frontier subdivision of the rapid reacting [ППШР]) implementation of complex of tasks (on a certain function [for example, function of fire protection of mark point of entrance-departure]) is provided for an achievement concretely of one quantitative result (parameter), for example in relation to the prognosis of amount of departures for the job a fire processing Together with that in the real variant when influence of external and internal factors is on the process of implementation of the functions (errors in a weekend given, insufficiency of resources and others like that) fixed on frontier subdivision, and also in connection with the methodical errors of planning of tasks in an organizational structure and in connection with a limit amount of the appraised variants of possible development of events (for the real terms and processes that have in the composition unforeseeable [to the case] sizes and factors) the got value of х of quantitative result that is examined can differ from ideal. For the estimation of losses of efficiency, that arise up at such inaccuracy in execution works from realization of the set function this size of losses of efficiency arc wise depends on the module of difference of ideal value and current and folds certain unit of efficiency on unit that answers величені at his insufficient value and the determined amount of units of efficiency, – at his surplus value. Thus, in the article the process of synthesis of expression of estimation of index of losses of efficiency is presented at implementation of works on a concrete function for an achievement concretely of one quantitative result (parameter). In further the got result it can be drawn on for the analysis of index of co-ordination of results of implementation of works on this function in the organizational structure of frontier subdivision that is examined.

Submodular functions are set functions mapping every subset of some ground set of size $n$ into the real numbers and satisfying the diminishing returns property. Submodular minimization is an important field in discrete optimization theory due to its relevance for various branches of mathematics, computer science and economics. The currently fastest strongly polynomial algorithm for exact minimization [LSW15] runs in time $\widetilde{O}(n^3 \cdot \mathrm{EO} + n^4)$ where $\mathrm{EO}$ denotes the cost to evaluate the function on any set. For functions with range $[-1,1]$, the best $\epsilon$-additive approximation algorithm [CLSW17] runs in time $\widetilde{O}(n^{5/3}/\epsilon^{2} \cdot \mathrm{EO})$. In this paper we present a classical and a quantum algorithm for approximate submodular minimization. Our classical result improves on the algorithm of [CLSW17] and runs in time $\widetilde{O}(n^{3/2}/\epsilon^2 \cdot \mathrm{EO})$. Our quantum algorithm is, up to our knowledge, the first attempt to use quantum computing for submodular optimization. The algorithm runs in time $\widetilde{O}(n^{5/4}/\epsilon^{5/2} \cdot \log(1/\epsilon) \cdot \mathrm{EO})$. The main ingredient of the quantum result is a new method for sampling with high probability $T$ independent elements from any discrete probability distribution of support size $n$ in time $O(\sqrt{Tn})$. Previous quantum algorithms for this problem were of complexity $O(T\sqrt{n})$.

Actuator placement is an active field of research, which has received significant attention for its applications in complex dynamical networks. In this article, we study the problem of finding a set of actuator placements minimizing the metric that measures the average energy consumed for state transfer by the controller, while satisfying a structural controllability requirement and a cardinality constraint on the number of actuators allowed. As no computationally efficient methods are known to solve such combinatorial set function optimization problems, two greedy algorithms, forward and reverse, are proposed to obtain approximate solutions. We first show that the constraint sets these algorithms explore can be characterized by matroids. We then obtain performance guarantees for the forward and reverse greedy algorithms applied to the general class of matroid optimization problems by exploiting properties of the objective function such as the submodularity ratio and the curvature. Finally, we propose feasibility check methods for both algorithms based on maximum flow problems on certain auxiliary graphs originating from the network graph. Our results are verified with case studies over large networks. ISSN:0018-9286 ISSN:1558-2523

In this paper, the problem we study is how to maximize a monotone non-submodular function with cardinality constraint. Different from the previous streaming algorithms, this paper mainly considers the sliding window model. Based on the concept of diminishing-return ratio [Formula: see text], we propose a [Formula: see text]-approximation algorithm with the memory [Formula: see text], where [Formula: see text] is the ratio between maximum and minimum values of any singleton element of function [Formula: see text]. Then, we improve the approximation ratio to [Formula: see text] through the sub-windows at the expense of losing some memory. Our results generalize the corresponding results for the submodular case.