For a function defined on the integer lattice, we consider discrete versions of midpoint convexity, which offer a unifying framework for discreteconvexity of functions, including integral convexity, L-(sic)-convexity...
详细信息
For a function defined on the integer lattice, we consider discrete versions of midpoint convexity, which offer a unifying framework for discreteconvexity of functions, including integral convexity, L-(sic)-convexity, and submodularity. By considering discrete midpoint convexity for all pairs at l(infinity)-distance equal to 2 or not smaller than 2, we identify new classes of discrete convex functions, called locally and globally discrete midpoint convexfunctions. These functions enjoy nice structural properties. They are stable under scaling and addition and satisfy a family of inequalities named parallelogram inequalities. Furthermore, they admit a proximity theorem with the same small proximity bound as that for L-(sic)-convexfunctions. These structural properties allow us to develop an algorithm for the minimization of locally and globally discrete midpoint convexfunctions based on the proximity-scaling approach and on a novel 2-neighborhood steepest descent algorithm.
Multimodular functions and L-convexfunctions have been investigated almost independently, but they are, in fact, equivalent objects that can be related through a unimodular coordinate transformation. Some facts known...
详细信息
Multimodular functions and L-convexfunctions have been investigated almost independently, but they are, in fact, equivalent objects that can be related through a unimodular coordinate transformation. Some facts known for L-convexfunctions can be translated to new results for multimodular functions, and vice versa. In particular, the local optimality condition for global optimality found in the literature of multimodular functions should be rectified, and a discrete separation theorem holds for multimodular functions.
We investigate an auction model where there are many different goods, each good has multiple units and bidders have gross substitutes valuations over the goods. We analyze the number of iterations in iterative auction...
详细信息
We investigate an auction model where there are many different goods, each good has multiple units and bidders have gross substitutes valuations over the goods. We analyze the number of iterations in iterative auction algorithms for the model based on the theory of discreteconvex analysis. By making use of L-h-convexity of the Lyapunov function we derive exact bounds on the number of iterations in terms of the l(infinity)-distance between the initial price vector and the found equilibrium. Our results extend and unify the price adjustment algorithms for the multi-unit auction model and for the unit-demand auction model, offering computational complexity results for these algorithms, and reinforcing the connection between auction theory and discreteconvex analysis. (C) 2016 Elsevier B.V. All rights reserved.
A function with one integer variable is defined to be integer convex by Fox [3] and Denardo [1] if its second forward differences are positive. In this paper, condense discreteconvexity of nonlinear discrete multivar...
详细信息
ISBN:
(纸本)9783642206610
A function with one integer variable is defined to be integer convex by Fox [3] and Denardo [1] if its second forward differences are positive. In this paper, condense discreteconvexity of nonlinear discrete multivariable functions with their corresponding Hessian matrices is introduced which is a generalization of the integer convexity definition of Fox [3] and Denardo [1] to higher din-tensional space Z(n). In addition, optimization results are proven for C-1 condense discrete convex functions assuming that the given condense discrete convex function is C-1. Yuceer [17] proves convexity results for a certain class of discrete convex functions and shows that the restriction of the adaptation of Rosenbrook's function from real variables to discrete variables does not yield a discretely convexfunction. Here it is shown that the adaptation of Rosenbrook's function considered in [17] is a condense discrete convex function where the set of local minimums is also the the set of global minimums.
Recently, András Sebo{combining double acute accent} and Nicola Apollonio considered the following generalization of the problem to determine a matching of size k. Given a graph G = (V, E) and an integer k, deter...
详细信息
L-convexfunctions are nonlinear discretefunctions on integer points that are computationally tractable in optimization. In this paper, a discrete Hessian matrix and a local quadratic expansion are defined for L-conv...
详细信息
L-convexfunctions are nonlinear discretefunctions on integer points that are computationally tractable in optimization. In this paper, a discrete Hessian matrix and a local quadratic expansion are defined for L-convexfunctions. We characterize L-convexfunctions in terms of the discrete Hessian matrix and the local quadratic expansion.
A min-max formula is proved for the minimum of an integer-valued separable discrete convex function in which the minimum is taken over the set of integral elements of a box total dual integral polyhedron. One variant ...
详细信息
A min-max formula is proved for the minimum of an integer-valued separable discrete convex function in which the minimum is taken over the set of integral elements of a box total dual integral polyhedron. One variant of the theorem uses the notion of conjugate function (a fundamental concept in nonlinear optimization), but we also provide another version that avoids conjugates, and its spirit is conceptually closer to the standard form of classic min-max theorems in combinatorial optimization. The presented framework provides a unified background for separable convex minimization over the set of integral elements of the intersection of two integral base-polyhedra, submodular flows, L-convex sets, and polyhedra defined by totally unimodular matrices. As an unexpected application, we show how a wide class of inverse combinatorial optimization problems can be covered by this new framework.
The concept of a jump system, introduced by Bouchet and Cunningham [SIAM J. discrete Math., 8 (1995), pp. 17-32], is a set of integer points with a certain exchange property. In this paper, we discuss several linear a...
详细信息
The concept of a jump system, introduced by Bouchet and Cunningham [SIAM J. discrete Math., 8 (1995), pp. 17-32], is a set of integer points with a certain exchange property. In this paper, we discuss several linear and convex optimization problems on jump systems and show that these problems can be solved in polynomial time under the assumption that a membership oracle for a jump system is available. We first present a polynomial-time implementation of the greedy algorithm for the minimization of a linear function. We then consider the minimization of a separable-convexfunction on a jump system and propose the. first polynomial-time algorithm for this problem. The algorithm is based on the domain reduction approach developed in Shioura [discrete Appl. Math., 84 (1998), pp. 215-220]. We. finally consider the concept of M-convexfunctions on constant-parity jump systems which has been recently proposed by Murota [SIAM J. discrete Math., 20 (2006), pp. 213-226]. It is shown that the minimization of an M-convexfunction can be solved in polynomial time by the domain reduction approach.
暂无评论