Cones of alternating and cut submodular set functions

We describe facets of the cones of alternating set functions and cut submodular set functions generated by directed and undirected graphs and by uniform even hypergraphs. This answers a question asked by L. Lovász at the Bonn Mathematical Programming Conference in 1982. We show that there is a network flow algorithm for minimizing a hypergraph cut set function.     

On submodular function minimization

Earlier work of Bixby, Cunningham, and Topkis is extended to give a combinatorial algorithm for the problem of minimizing a submodular function, for which the amount of work is bounded by a polynomial in the size of the underlying set and the largest function value (not its length). Research partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada.     

Directed submodularity,ditroids and directed submodular flows

Set relations and operations such as inclusion, union and intersection are generalized to directed subsets whose elements are distinguished between forward and backward elements. The concepts of submodular functions, matroids and polymatroidal network flows are extended to the concepts of directed submodular functions, ditroids and directed submodular flows on directed subsets. Two unrelated matroids (submodular functions) can be embedded in one ditroid (directed submodular function). Total dual integrality is preserved in these generalizations and proved for very general set-function class-directed odd submodular functions.This work was partially supported by Chinese National Natural Science Fund.     

Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions

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. This work is supported by the Alexander von Humboldt fellowship (1982/83), West Germany.     

Principal structure of submodular systems and hitchcock-type independent flows

This paper discusses the principal structure of submodular systems due to S. Fujishige. It is shown that the principal structure is the coarsest decomposition that is finer than any decomposition induced by the principal partition with respect to a minimal nonnegative superbase. The concept of Hitchcock-type independent flow is introduced so that previously known results on the principal structures for bipartite matchings, layered mixed matrices and independent matchings can be understood as applications of the present result.     

Decomposition of partial orders

A decomposition theory for partial orders which arises from the split decomposition of submodular functions is introduced. As a consequence of this theory, any partial order has a unique decomposition consisting of indecomposable partial orders and certain highly decomposable partial orders. The highly decomposable partial orders are completely characterized. As a special case of partial orders, we consider lattices and distributive lattices. It occurs, that the highly decomposable distributive lattices are precisely the Boolean lattices.     

Periodic interpolation and wavelets on sparse grids

Nested spaces of multivariate periodic functions forming a non-stationary multiresolution analysis are investigated. The scaling functions of these spaces are fundamental polynomials of Lagrange interpolation on a sparse grid. The approach based on Boolean sums leads to sample and wavelet spaces of significantly lower dimension and good approximation order. The algorithms for complete decomposition and reconstruction are of simple structure and low complexity. This revised version was published online in June 2006 with corrections to the Cover Date.     

Minimization on submodular flows

Edmonds and Giles [1] discuss functions on the arcs of a digraph satisfying submodular set constraints. We call such functions submodular flows, show that the difference of group-valued submodular flows is a network circulation in a certain auxiliary digraph, and derive a criterion for the existence of group-valued submodular flows. We develop a method for maximizing the value of a group-valued submodular flow in a specified arc and a negative circuit method for minimizing certain functions on ring-valued submodular flows. In particular, algebraic linear functions over modules and certain semimodules as well as quotients of linear functions over totally ordered, commutative fields can be minimized.     

The expressive power of binary submodular functions

We investigate whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This question has been considered in several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively.Our results have several corollaries. First, we characterise precisely which submodular polynomials of arity 4 can be expressed by binary submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities which can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish, for the first time, that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.     

The edmonds—Gallai decomposition for matchings in locally finite graphs

We show that the Edmonds—Gallai decomposition theorem for matchings in finite graphs generalizes to all locally finite graphs. C.N.R.S. Dedicated to Tibor Gallai on his seventieth birthday     

A capacity scaling algorithm for convex cost submodular flows

This paper presents a scaling scheme for submodular functions. A small but strictly submodular function is added before scaling so that the resulting functions should be submodular. This scaling scheme leads to a weakly polynomial algorithm to solve minimum cost integral submodular flow problems with separable convex cost functions, provided that an oracle for exchange capacities is available.     

Structural theorems for submodular functions,polymatroids and polymatroid intersections

This paper presents a lattice-theoretic decomposition method for submodular functions. This decomposition is derived from a lattice, called a skeleton, which has the property that the specified submodular function is reduced to be modular on it.Several types of skeletons arise from the various kinds of minimization problems of submodular functions. The minimization problem associated with the well-known min-max eqaulity of the polymatroid intersection problem affords a skeleton, which is shown to provide a direct-sum decomposition of the maximum common independent vectors, i.e. the solutions of the intersection problem. Furthermore, a parametrized polymatroid intersection problem is considered and the construction of its solution, called a universal pair, is described. This paper consists of the main results of the author's unpublished works [27], [35].     

Canonical decompositions of symmetric submodular systems

Let E be a finite set, R be the set of real numbers and f: 2^E→R be a symmetric submodular function. The pair (E,f) is called a symmetric submodular system. We examine the structures of symmetric submodular systems and provide a decomposition theory of symmetric submodular systems. The theory is a generalization of the decomposition theory of 2-connected graphs developed by Tutte and can be applied to any (symmetric) submodular systems.     

The Calderón reproducing formula, windowed X-ray transforms, and radon transforms in LP-spaces

The generalized Calderón reproducing formula involving “wavelet measure” is established for functions f ∈ L^p(ℝⁿ). The special choice of the wavelet measure in the reproducing formula gives rise to the continuous decomposition of f into wavelets, and enables one to obtain inversion formulae for generalized windowed X-ray transforms, the Radon transform, and k-plane transforms. The admissibility conditions for the wavelet measure μ are presented in terms of μ itself and in terms of the Fourier transform of μ. Acknowledgements and Notes. Partially sponsored by the Edmund Landau Center for research in Mathematical Analysis, supported by the Minerva Foundation (Germany).     

Discrete convex analysis

A theory of “discrete convex analysis” is developed 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, subgradients, the Fenchel min-max duality, separation theorems and the Lagrange duality framework for convex/nonconvex optimization. The technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms. Sections 1–4 extend the conjugacy relationship between submodularity and exchange ability, deepening our understanding of the relationship between convexity and submodularity investigated in the eighties by A. Frank, S. Fujishige, L. Lovász and others. Sections 5 and 6 establish duality theorems for M- and L-convex functions, namely, the Fenchel min-max duality and separation theorems. These are the generalizations of the discrete separation theorem for submodular functions due to A. Frank and the optimality criteria for the submodular flow problem due to M. Iri-N. Tomizawa, S. Fujishige, and A. Frank. A novel Lagrange duality framework is also developed in integer programming. We follow Rockafellar’s conjugate duality approach to convex/nonconvex programs in nonlinear optimization, while technically relying on the fundamental theorems of matroid-theoretic nature.     

Structural properties of greedoids

Greedoids were introduced by the authors as generalizations of matroids providing a framework for the greedy algorithm. In this paper they are studied from a structural aspect. Definitions of basic matroid-theoretical concepts such as rank and closure can be generalized to greedoids, even though they loose some of their fundamental properties. The rank function of a greedoid is only “locally” submodular. The closure operator is not monotone but possesses a (relaxed) Steinitz—McLane exchange property. We define two classes of subsets, called rank-feasible and closure-feasible, so that the rank and closure behave nicely for them. In particular, restricted to rank-feasible sets the rank function is submodular. Finally we show that Rado’s theorem on independent transversals of subsets of matroids remains valid for feasible transversals of certain sets of greedoids. Dedicated to Paul Erdős on his seventieth birthday Supported by the joint research project “Algorithmic Aspects of Combinatorial Optimization” of the Hungarian Academy of Sciences (Magyar Tudományos Akadémia) and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 21).     

Probability set functions

A probability set function is interpretable as a probability distribution on binary sequences of fixed length. Cumulants of probability set functions enjoy particularly simple properties which make them more manageable than cumulants of general random variables. We derive some identities satisfied by cumulants of probability set functions which we believe to be new. Probability set functions may be expanded in terms of their cumulants. We derive an expansion which allows the construction of examples of probability set functions whose cumulants are arbitrary, restricted only by their absolute values. It is known that this phenomenon cannot occur for continuous probability distributions. Some particular examples of probability set functions are considered, and their cumulants are computed, leading to a conjecture on the upper bound of the values of cumulants. Moments of probability set functions determined by arithmetical conditions are computed in a final example.Dedicated to our friend, W.A. Beyer. Financial support for this work was derived from the U.S.D.O.E. Human Genome Project, through the Center for Human Genome Studies at Los Alamos National Laboratory, and also through the Center for Nonlinear Studies, Los Alamos National Laboratory, LANL report LAUR-97-323.     

Circle decompositions of surfaces

We determine which connected surfaces can be partitioned into topological circles. There are exactly seven such surfaces up to homeomorphism: those of finite type, of Euler characteristic zero, and with compact boundary components. As a byproduct, we get that any circle decomposition of a surface is upper semicontinuous.     

Indecomposable decomposition of tensor products of modules over Drinfeld doubles of Taft algebras

In this paper, we study the tensor product structure of the category of finite dimensional modules over Drinfeld doubles of Taft Hopf algebras. Tensor product decomposition rules for all finite dimensional indecomposable modules are explicitly given.