Buneman's decomposition of a metric can be obtained in a geometric way as the polyhedral split decomposition of a polyhedral convexfunction associated with a metric. In discrete convex analysis, such a polyhedral...
详细信息
Buneman's decomposition of a metric can be obtained in a geometric way as the polyhedral split decomposition of a polyhedral convexfunction associated with a metric. In discrete convex analysis, such a polyhedral convexfunction is considered as an important example of m-convex functions. motivated by this, we shed light on the decomposition from the viewpoint of discrete convex analysis. We firstly show that the decomposition is a sum of m-convex functions, where a sum of m-convex functions is not necessarily m-convex in general. We explain why the m-convexity is preserved in the decomposition. We next show that a quadratic m-convex function is split-decomposable at every point. This indicates simplicity of the geometric structure of a quadratic m-convex function. We finally give a characterization of m-convex polyhedra in terms of their facets. This can be used to describe the m-convexity of a polyhedron associated with a function on a cross-free family.
This is a survey of algorithmic results in the theory of "discrete convex analysis" for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering...
详细信息
This is a survey of algorithmic results in the theory of "discrete convex analysis" for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, the Fenchel min-max duality, and separation theorems. The technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms.
In 1979, in an interesting paper, R.J. morris introduced the notion of convex set function defined on an atomless finite measure space. After a short period this notion, as well as generalizations of it, began to be s...
详细信息
In 1979, in an interesting paper, R.J. morris introduced the notion of convex set function defined on an atomless finite measure space. After a short period this notion, as well as generalizations of it, began to be studied in several papers. The aim was to obtain results similar to those known for usual convex (or generalized convex) functions. Unfortunately several notions are ambiguous and the arguments used in the proofs of several results are not clear or not correct. In this way there were stated even false results. The aim of this paper is to point out that using some simple ideas it is possible, on one hand, to deduce the correct results by means of convex analysis and, on the other hand, to emphasize the reasons for which there are problems with other results. (c) 2006 Elsevier Inc. All rights reserved.
Let T be a tree with a vertex set {1, 2 ,..., N}. Denote by d(ij) the distance between vertices i and j. In this paper, we present an explicit combinatorial formula of principal minors of the matrix (t(dij)), and its ...
详细信息
Let T be a tree with a vertex set {1, 2 ,..., N}. Denote by d(ij) the distance between vertices i and j. In this paper, we present an explicit combinatorial formula of principal minors of the matrix (t(dij)), and its applications to tropical geometry, study of multivariate stable polynomials, and representation of valuated matroids. We also give an analogous formula for a skew-symmetric matrix associated with T. (C) 2015 Elsevier Inc. All rights reserved.
In this paper, three fundamental and important Riemann-Liouville fractional integral identities including a twice differentiable mapping are established. Secondly, some interesting Hermite-Hadamard type inequalities i...
详细信息
In this paper, three fundamental and important Riemann-Liouville fractional integral identities including a twice differentiable mapping are established. Secondly, some interesting Hermite-Hadamard type inequalities involving Riemann-Liouville fractional integrals for m-convexity and (s, m)-convexity functions, respectively, by virtue of the established integral identities are presented.
In this paper, some new inequalities of the Hermite-Hadamard type for the classes of functions whose derivatives' absolute values arem-convex and(alpha,m)-convex are obtained. The results obtained in this work ext...
详细信息
In this paper, some new inequalities of the Hermite-Hadamard type for the classes of functions whose derivatives' absolute values arem-convex and(alpha,m)-convex are obtained. The results obtained in this work extend and improve the corresponding ones in the literature. Some applications to special means of real numbers are also given.
For an undirected graph and a fixed integer k, a 2-matching is said to be k-restricted if it has no cycle of length k or less. The problem of finding a maximum cardinality k-restricted 2-matching is polynomially solva...
详细信息
For an undirected graph and a fixed integer k, a 2-matching is said to be k-restricted if it has no cycle of length k or less. The problem of finding a maximum cardinality k-restricted 2-matching is polynomially solvable when k <= 3, and NP-hard when k >= 5. On the other hand, the degree sequences of the k-restricted 2-matchings form a jump system for k <= 3, and do not always form a jump system for k >= 5, which is consistent with the polynomial solvability of the maximization problem. In 2002, Cunningham conjectured that the degree sequences of 4-restricted 2-matchings form a jump system and the maximum cardinality 4-restricted 2-matching can be found in polynomial time. In this paper, we show that the first conjecture is true, that is, the degree sequences of 4-restricted 2-matchings form a jump system. We also show that the maximum weight 4-restricted 2-matchings in a bipartite graph induce an m-concave function on the jump system if and only if the weight function is vertex-induced on every square. This result is also consistent with the polynomial solvability of the maximum weight 4-restricted 2-matching problem in bipartite graphs. (C) 2012 Elsevier Inc. All rights reserved.
作者：
murota, KUniv Tokyo
Grad Sch Informat Sci & Technol Tokyo 1138656 Japan JST
PRESTO Tokyo 1138656 Japan
This paper investigates the complexity of steepest descent algorithms for two classes of discrete convexfunctions: m-convex functions and L-convexfunctions. Simple tie-breaking rules yield complexity bounds that are...
详细信息
This paper investigates the complexity of steepest descent algorithms for two classes of discrete convexfunctions: m-convex functions and L-convexfunctions. Simple tie-breaking rules yield complexity bounds that are polynomials in the dimension of the variables and the size of the effective domain. Combining the present results with a standard scaling approach leads to an efficient algorithm for L-convexfunctionminimization.
The main objective of this article is to introduce a new class of real valued functions that include the well-known class of -convexfunctions introduced by Toader (1984). The members of this collection are called Jen...
详细信息
The main objective of this article is to introduce a new class of real valued functions that include the well-known class of -convexfunctions introduced by Toader (1984). The members of this collection are called Jensen -convex and are defined, for , via the functional inequality where . These functions generate a new kind of functional convexity that is studied in terms of its behavior with respect to basic algebraic operations such as sums, products, compositions, etc. in this paper. In particular, it is proved that any starshaped Jensen convexfunction is Jensen -convex. At the same time an interesting example (Example 3) shows how the classes of Jensen -convexfunctions depend on . All the techniques employed come from traditional basic calculus and most of the calculations have been done with mathematica 8.0.0 and validated with maple 15 as well as all the figures included.
A jump system, which is a set of integer lattice points with an exchange property, is all extended concept of a matroid. Some combinatorial Structures Such as the degree sequences of the matchings in all undirected gr...
详细信息
A jump system, which is a set of integer lattice points with an exchange property, is all extended concept of a matroid. Some combinatorial Structures Such as the degree sequences of the matchings in all undirected graph are known to form a jump system. On the other hand, the maximum even factor problem is a generalization of the maximummatching problem into digraphs. When the given digraph has a certain property called odd-cycle-symmetry, this problem is polynomially solvable. The main result of this paper is that the degree sequences of all even factors in a digraph form a jump system if and only if the digraph is odd-cycle-symmetric. Furthermore, as a generalization, we show that the weighted even factors induce all m-convex (m-concave) function on a constant-parity jump system. These results suggest that even factors are a natural generalization of matchings and the assumption of odd-cycle-symmetry of digraphs is essential. (C) 2008 Elsevier Inc. All rights reserved.
暂无评论