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.     

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.     

Optimization over the polyhedron determined by a submodular function on a co-intersecting family

A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities.     

Increasing the rooted-connectivity of a digraph by one

In order to unify these approaches, here we describe a two-phase greedy algorithm working on a slight extension of lattice polyhedra. This framework includes the rooted node-connectivity augmentation problem, as well, and hence the resulting algorithm, when appropriately specialized, finds a minimum cost of new edges whose addition to a digraph increases its rooted connectivity by one. The only known algorithm for this problem used submodular flows. Actually, the specialized algorithm solves an extension of the rooted edge-connectivity and node-connectivity augmentation problem. Received December 1996 / Revised version received January 1998 Published online March 16, 1999     

Inverse Problems of Submodular Functions on Digraphs

In this paper, we study the inverse problem of submodular functions on digraphs. Given a feasible solution x* for a linear program generated by a submodular function defined on digraphs, we try to modify the coefficient vector c of the objective function, optimally and within bounds, such that x* becomes an optimal solution of the linear program. It is shown that the problem can be formulated as a combinatorial linear program and can be transformed further into a minimum cost circulation problem. Hence, it can be solved in strongly polynomial time. We also give a necessary and sufficient condition for the feasibility of the problem. Finally, we extend the discussion to the version of the inverse problem with multiple feasible solutions.     

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.     

次模函数最大化的流算法综述

次模函数优化在计算机科学、数学、经济学等学科得到广泛研究.大数据环境下的次模优化是相对较新的研究领域,受到更多关注.特别地,考虑基于流模型的次模最大化问题.在该问题中,数据以流的形式呈现,其目的是从数据流中抽取满足某些特性的稀疏子集,最大化次模收益函数值.介绍了基于流模型的次模最大化问题的阈值和优先权方法,同时也介绍了若干次模最大化变形的流算法进展.     

Decomposition of submodular functions

A decomposition theory for submodular functions is described. Any such function is shown to have a unique decomposition consisting of indecomposable functions and certain highly decomposable functions, and the latter are completely characterized. Applications include decompositions of hypergraphs based on edge and vertex connectivity, the decomposition of matroids based on three-connectivity, the Gomory—Hu decomposition of flow networks, and Fujishige’s decomposition of symmetric submodular functions. Efficient decomposition algorithms are also discussed.     

The ellipsoid method and its consequences in combinatorial optimization

L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields a proof that weighted fractional chromatic number is NP-hard. Research by the third author was supported by the Netherlands Organisation for the Advancement of Pure Research (Z.W.O.).     

Excluding a Simple Good Pair Approach to Directed Cuts

In 1972, Mader proved that every undirected graph has a good pair, that is, an ordered pair (u,v) of nodes such that the star of v is a minimum cut separating u and v. In 1992, Nagamochi and Ibaraki gave a simple procedure to find a good pair as the basis of an elegant and very efficient algorithm to find minimum cuts in graphs. This paper rules out the simple good pair approach for the problem of finding a minimum directed cut in a digraph and for the more general problem of minimizing submodular functions. In fact, we construct a digraph with no good pair. Note that if a graph has no good pair, then it may not possess a so-called cut-equivalent tree. Benczúr constructed a digraph with no cut-equivalent tree; our counterexample thus extends Benczúr's one. Received: March 12, 1999 Final version received: June 19, 2000     

Pseudo-differential operators and Markov semigroups on compact Lie groups

We extend the Ruzhansky-Turunen theory of pseudo-differential operators on compact Lie groups into a tool that can be used to investigate group-valued Markov processes in the spirit of the work in Euclidean spaces of N. Jacob and collaborators. Feller semigroups, their generators and resolvents are exhibited as pseudo-differential operators and the symbols of the operators forming the semigroup are expressed in terms of the Fourier transform of the transition kernel. The symbols are explicitly computed for some examples including the Feller processes associated to stochastic flows arising from solutions of stochastic differential equations on the group driven by Lévy processes. We study a family of Lévy-type linear operators on general Lie groups that are pseudo-differential operators when the group is compact and find conditions for them to give rise to symmetric Dirichlet forms.     

Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2

It has widely been recognized that submodular set functions and base polyhedra associated with them play fundamental and important roles in combinatorial optimization problems. In the present paper, we introduce a generalized concept of base polyhedron. We consider a class of pointed convex polyhedra in R^V whose edge vectors have supports of size at most 2. We call such a convex polyhedron a polybasic polyhedron. The class of polybasic polyhedra includes ordinary base polyhedra, submodular/supermodular polyhedra, generalized polymatroids, bisubmodular polyhedra, polybasic zonotopes, boundary polyhedra of flows in generalized networks, etc. We show that for a pointed polyhedron PR^V, the following three statements are equivalent:

(1) P is a polybasic polyhedron.

(2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes.

(3) The support function of P is a submodular function on each orthant of R^V.

This reveals the geometric structure of polybasic polyhedra and its relation to submodularity.     

Supermodularity in Various Partition Problems

Supermodular and submodular functions have attracted a great deal of attention since the seminal paper of Lovász. Recently, supermodular functions were studied in the context of some optimal partition problems. We completely answer a question arisen there whether a certain partition function is supermodular.     

Group-valued measures on coarse-grained quantum logics

In [3] it was shown that a (real) signed measure on a cyclic coarse-grained quantum logic can be extended, as a signed measure, over the entire power algebra. Later ([9]) this result was re-proved (and further improved on) and, moreover, the non-negative measures were shown to allow for extensions as non-negative measures. In both cases the proof technique used was the technique of linear algebra. In this paper we further generalize the results cited by extending group-valued measures on cyclic coarse-grained quantum logics (or non-negative group-valued measures for lattice-ordered groups). Obviously, the proof technique is entirely different from that of the preceding papers. In addition, we provide a new combinatorial argument for describing all atoms of cyclic coarse-grained quantum logics.     

Additive envelopes of continuous functions

We present an iterative method for constructing additive envelopes of continuous functions on a compact set, with contact at a specified point. For elements of a class of submodular functions we provide closed-form expressions for such additive envelopes.     

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.     

Maximizing non-monotone submodular set functions subject to different constraints: Combined algorithms

We study the problem of maximizing constrained non-monotone submodular functions and provide approximation algorithms that improve existing algorithms in terms of either the approximation factor or simplicity. Different constraints that we study are exact cardinality and multiple knapsack constraints for which we achieve (0.25−?)-factor algorithms.We also show, as our main contribution, how to use the continuous greedy process for non-monotone functions and, as a result, obtain a 0.13-factor approximation algorithm for maximization over any solvable down-monotone polytope.     

Modular functions: Uniform boundedness and compactness

We prove the Nikodym Boundedness, Brooks-Jewett and Vitali-Hahn-Saks theorems for modular functions on orthomodular lattices with SIP and on particular complemented or sectionally complemented lattices, and the equivalence, for any complemented or sectionally complemented lattice, between the Brooks-Jewett and Vitali-Hahn-Saks theorems for group-valued modular functions. As consequence, we obtain characterizations of relative, sequential and weak compactness in spaces of modular functions.