Search

A transshipment problem with demands that exceed network capacity can be solved by sending flow in several waves. How can this be done in the minimum number, T, of waves, and at minimum cost, if costs are piecewise linear convex functions of the flow? In this paper, we show that this problem can be solved using min{m, log T, log(mΓU) / 1+log(mΓU)-log(mU)} maximum flow computations and one minimum (convex) cost flow computation. Here m is the number of arcs, Γ is the maximum supply or demand, and U is the maximum capacity. When there is only one sink, this problem can be solved in the same asymptotic time as one minimum (convex) cost flow computation. This improves upon the previous best algorithm to solve the problem without costs by a factor of k. Our solutions start with a stationary fractional flow and use rounding to transform this into an integral flow. The rounding procedure takes O(n) time. [ABSTRACT FROM AUTHOR]

Let C be a full-dimensional pointed closed convex cone in ℝm obtained by taking the conic hull of a strictly convex set. Given A ∈ ..., B ∈ ..., and b ∈ ℚm, a simple conic mixed-integer set (SCMIS) is a set of the form {(x, y) ∈ ... x ... | Ax + By - b ∈ C}. In this paper, we give a complete characterization of the closedness of convex hulls of SCMISs. Under certain technical conditions on the cone C, we show that the closedness characterization can be used to construct a polynomial-time algorithm to check the closedness of convex hulls of SCMISs. Moreover, we also show that the Lorentz cone satisfies these technical conditions. In the special case of pure integer problems, we present sufficient conditions, which can be checked in polynomial time, to verify the closedness of intersection of SCMISs. [ABSTRACT FROM AUTHOR]

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-convex function 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-convex functions 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-convex function can be solved in polynomial time by the domain reduction approach. [ABSTRACT FROM AUTHOR]

A jump system is a set of integer points with an exchange property, which is a generalization of a matroid, a delta-matroid, and a base polyhedron of an integral polymatroid (or a submodular system). Recently, the concept of M-convex functions on constant-parity jump systems was introduced by Murota as a class of discrete convex functions that admit a local criterion for global minimality. M-convex functions on constant-parity jump systems generalize valuated matroids, valuated delta-matroids, and M-convex functions on base polyhedra. This paper reveals that the class of M-convex functions on constant-parity jump systems is closed under a number of natural operations such as splitting, aggregation, convolution, composition, and transformation by networks. The present results generalize hitherto-known similar constructions for matroids, deltamatroids, valuated matroids, valuated delta-matroids, and M-convex functions on base polyhedra. [ABSTRACT FROM AUTHOR]

The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts. Minimizing a nonnegative linear function over the cut dominant is equivalent to finding a minimum weight cut in the graph. We give a forbidden-minor characterization of the graphs whose cut dominant can be defined by inequalities with integer coefficients and right-hand side at most 2. Our result is related to the forbidden-minor characterization of TSP-perfect graphs by Fonlupt and Naddef [Math. Program, 53 (1992), pp. 147-172]. We show how to derive each of the results from the other. Furthermore, we establish general properties of forbidden minors for right-hand sides larger than 2. [ABSTRACT FROM AUTHOR]

The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given planar convex body was initiated by Mazurkiewicz in 1916. Such a collection forms an opaque barrier for the convex body. In 1991, Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex n-gon. He conjectured that the barrier found by his algorithm is optimal, but this was refuted recently by Provan et al. Here, we give a Shermer-like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in O(n) time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm. [ABSTRACT FROM AUTHOR]

Murota et al. have recently developed a theory of discrete convex analysis which concerns M-convex functions on jump systems. We introduce here a family of M-concave functions arising naturally from polynomials (over a field of generalized Puiseux series) with prescribed non-vanishing properties. This family contains several of the most well studied M-concave functions in the literature. In the language of tropical geometry, we study the tropicalization of the space of polynomials with the half-plane property and show that it is strictly contained in the space of M-concave functions. We also provide a short proof of Speyer's "hive theorem" which he used to give a new proof of Horn's conjecture on eigenvalues of sums of Hermitian matrices. [ABSTRACT FROM AUTHOR]

We provide a polynomial algorithm that determines for any given undirected graph G = (V,E), positive integer k, and convex functions fu : N → R (v ϵ V ) a subgraph H = (V, F) of k edges that minimizes Σ u ϵ v fv(dH(v)), where dH(v) is the degree of v in H. The motivation and at the same time the main application of the results is the problem of finding a subset of k vertices in a line graph that covers as many edges as possible. The latter problem generalizes the vertex cover problem for line graphs, which is in turn equivalent to the maximum matching problem in graphs. Improving paths or walks for factorization problems have to be completed by pairs of such walks for this problem. We provide several solutions leading to different variants of the problem and also show the limits of the methods by proving the NP-completeness of some direct extensions, in particular to all convex functions. [ABSTRACT FROM AUTHOR]

Motivated by L(p, q)-labelings of graphs, we introduce a notion of λ-graphs: a λ-graph G is a graph with two types of edges: 1-edges and x-edges. For a parameter x ∈ [0, 1], a proper labeling of G is a labeling of vertices of G by nonnegative reals such that the labels of the endvertices of a 1-edge differ by at least 1 and the labels of the endvertices of an x-edge differ by at least x; λG (x) is the smallest real such that G has a proper labeling by labels from the interval [0,λG (x)]. We study properties of the function λG (x) for finite and infinite λ-graphs and establish the following results: if the function λG(x) is well defined, then it is a piecewise linear function of x with finitely many linear parts. Surprisingly, the set λ(α,β) of all functions λG with λG(0) = α and λG(1) = β is finite for any α≤β. We also prove a tight upper bound on the number of segments for finite λ-graphs G with convex functions λG(x). [ABSTRACT FROM AUTHOR]

The concept of M-convex functions is generalized for functions defined on constant-parity jump systems. M-convex functions arise from minimum weight perfect b-matchings and from a separable convex function (sum of univariate convex functions) on the degree sequences of an undirected graph. As a generalization of a recent result of Apollonio and Sebő for the minsquare factor problem, a local optimality criterion is given for minimization of an M-convex function subject to a component sum constraint. [ABSTRACT FROM AUTHOR]

We study optimization problems over partitions of the finite set N = {1,..., n}, where each element i in the partitioned set N is associated with a real number θi and the objective associated with a partition π = (πp,..., πp) has the form F(π) = f(θπ), where θπ = (Σi∈π1θi,....,Σi∈πpθi). When F is to be either maximized or minimized, we obtain conditions that allow for simple constructions of partitions that are uniformly optimal for all Schur convex functions f. [ABSTRACT FROM AUTHOR]