The supermodular order on multivariate distributions has many applications in financial and actuarial mathematics. In the particular case of finite, discrete distributions, we generalize the order to distributions on ...
详细信息
The supermodular order on multivariate distributions has many applications in financial and actuarial mathematics. In the particular case of finite, discrete distributions, we generalize the order to distributions on finite lattices. In this setting, we focus on the generating cone of supermodular functions because the extreme rays of that cone (modulo the modular functions) can be used as test functions to determine whether two random variables are ordered under the supermodular order. We completely determine the extreme supermodular functions in some special cases.
We introduce the concepts of phi-complete mixability and phi-joint mixability and we investigate some necessary and sufficient conditions to the phi-mixability of a set of distribution functions for some supermodular ...
详细信息
We introduce the concepts of phi-complete mixability and phi-joint mixability and we investigate some necessary and sufficient conditions to the phi-mixability of a set of distribution functions for some supermodular functions phi. We give examples and numerical verifications which confirm our findings. (C) 2015 Elsevier B.V. All rights reserved.
作者：
Jia, HaoDeakin Univ
Dept Econ 1 Gheringhap St Geelong Vic 3220 Australia
This paper complements Jia (2019) by proving that the even split rule is the only Pareto efficient allocation that breaks down any concave symmetric supermodular function into two supermodular functions. It further pr...
详细信息
This paper complements Jia (2019) by proving that the even split rule is the only Pareto efficient allocation that breaks down any concave symmetric supermodular function into two supermodular functions. It further provides an alternative proof for Theorem 1 of Jia (2019), which confirms that the even split rule is necessary to ensure any symmetric supermodular function, regardless its convexity or concavity, could be divided into two supermodular functions. (C) 2019 Elsevier B.V. All rights reserved.
We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without constraints. We define a convex (or concave) conjugate function of a submodular (or superm...
详细信息
We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without constraints. We define a convex (or concave) conjugate function of a submodular (or supermodular) function and show a Fenchel-type min-max theorem for submodular and supermodular functions. We also define a subgradient of a submodular function and derive a necessary and sufficient condition for a feasible solution of a submodular program to be optimal, which is a counterpart of the Karush-Kuhn-Tucker condition for convex programs.
We define the base polytope B(P, g) of partially ordered set P and a supermodular function g on the ideals of P as the convex hull of the incidence vectors of all linear extensions of P. This new class of polytopes co...
详细信息
We define the base polytope B(P, g) of partially ordered set P and a supermodular function g on the ideals of P as the convex hull of the incidence vectors of all linear extensions of P. This new class of polytopes contains, among others, the base polytopes of supermodular systems and permutahedra as special cases. After introducing the notion of compatibility for g, we give a complete linear description of B(P, g) for series-parallel posets and compatible functions g. In addition, we describe a greedy-type procedure which exhibits Sidney's job sequencing algorithm to minimize the total weighted completion time as a natural extension of the matroidal greedy algorithm from sets to posets. (C) 1998 The Mathematical Programing Society, Inc. Published by Elsevier Science B.V.
We study the property of dependence in lag for Markov chains on countable partially ordered state spaces and give conditions which ensure that a process is monotone in lag. In case of linearly ordered state spaces, pr...
详细信息
We study the property of dependence in lag for Markov chains on countable partially ordered state spaces and give conditions which ensure that a process is monotone in lag. In case of linearly ordered state spaces, proofs are based on the Lorentz inequality. However, we show that on partially ordered spaces Lorentz inequality is only true under additional assumptions. By using supermodular-type stochastic orders we derive comparison inequalities that compare the internal dependence structure of processes with that of their speeding-down versions. Applications of the results are presented for degradable exponential networks in which the nodes are subject to random breakdowns and repairs. We obtain comparison results for the breakdown processes as well as for the queue length processes that are not even Markovian on their own.
We generalize the concept of K-convexity to an n- dimensional Euclidean space. The resulting concept of K-convexity is useful in addressing production and inventory problems where there are individual product setup co...
详细信息
We generalize the concept of K-convexity to an n- dimensional Euclidean space. The resulting concept of K-convexity is useful in addressing production and inventory problems where there are individual product setup costs and/or joint setup costs. We derive some basic properties of K-convex functions. We conclude the paper with some suggestions for future research.
This paper highlights how a general class of hub location problems can be modeled as the minimization of a real-valued supermodular set function. Well-known problems such as uncapacitated hub location, p-hub median, a...
详细信息
This paper highlights how a general class of hub location problems can be modeled as the minimization of a real-valued supermodular set function. Well-known problems such as uncapacitated hub location, p-hub median, and hub arc location, among others, are shown to be particular cases of this class. Two integer programming formulations are introduced and compared. One uses path-based variables, frequently employed in hub location, whereas the other exploits properties of supermodular functions. In addition, several worst case bounds for a greedy and a local improvement heuristic are obtained for the general class and for some particular cases in which sharper bounds can be devised. Computational experiments are performed to compare both formulations when used with a general purpose solver. Computational results obtained on benchmark instances confirm the superiority of the supermodular formulation.
This paper considers queues with a Markov renewal arrival process and a particular transition matrix for the underlying Markov chain. Wt study the effect that the transition matrix has on the waiting time of the nth c...
详细信息
This paper considers queues with a Markov renewal arrival process and a particular transition matrix for the underlying Markov chain. Wt study the effect that the transition matrix has on the waiting time of the nth customer as well as on the stationary waiting time. The main theorem generalizes results of Szekli et al. (1994a) and partly confirms their conjecture. In this context we show the importance of a new stochastic ordering concept.
In a model of network communication based on a random walk in an undirected graph, what subset of nodes (subject to constraints on the set size), enables the fastest spread of information? The dynamics of spread is de...
详细信息
In a model of network communication based on a random walk in an undirected graph, what subset of nodes (subject to constraints on the set size), enables the fastest spread of information? The dynamics of spread is described by a process dual to the movement from informed to uninformed nodes. In this setting, an optimal set A minimizes the sum of the expected first hitting times F(A), of random walks that start at nodes outside the set. Identifying such a set is a problem in combinatorial optimization that is probably NP hard. F has been shown to be a supermodular and non-increasing set function and fortunately some results on optimization of such functions exist, e.g., in the work of Ilev. In this paper, the problem is reformulated so that the search for solutions to the problem is restricted to a class of optimal and "near" optimal subsets of the graph. We introduce a submodular, non-decreasing rank function., that permits some comparison between the solution obtained by the classical greedy algorithm and one obtained by our methods. The supermodularity and non-increasing properties of F are used to show that the rank of our solution is at least (1 - 1/e) times the rank of the optimal set. When the solution has a higher rank than the greedy solution this. constant can be improved to (1 + chi) (1 - 1/e) where chi > 0 is determined a posteriori. The method requires the evaluation of F for sets of some fixed cardinality m, where m is much smaller than the cardinality of the optimal set. Given nu = rho(A), a class of examples is presented that illustrate the tradeoff between m and solution quality nu.
暂无评论