Huber and Kolmogorov [Towards minimizing $k$-submodular functions, in Proceedings of ISCO 2012, Lecture Notes in Comput. Sci. 7422, Springer, Heidelberg, 2012, pp. 451--462] introduced a concept of $k$-submodular function as a generalization of ordinary submodular (set) functions and bisubmodular functions and obtained a min-max theorem for the minimization of $k$-submodular functions. Also Kuivinen [Discrete Optim., 8 (2011), pp. 459--477] considered submodular functions on (product lattices of) diamonds and showed a min-max theorem for the minimization of submodular functions on diamonds. In the present paper we consider a common generalization of $k$-submodular functions and submodular functions on diamonds, which we call a transversal submodular function (a t-submodular function, for short). We show a min-max theorem for the minimization of t-submodular functions in terms of a new norm composed of $\ell_1$ and $\ell_\infty$ norms. This reveals a relationship between the obtained min-max theorem and that for the minimization of ordinary submodular set functions due to Edmonds [Submodular functions, matroids, and certain polyhedra, in Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Gordon and Breach, New York, 1970, pp. 69--87].We also show how our min-max theorem for t-submodular functions can be used to prove the min-max theorem for $k$-submodular functions by Huber and Kolmogorov and that for submodular functions on diamonds by Kuivinen. Moreover, we show a counterexample to a characterization, given by Huber and Kolmogorov [Towards minimizing $k$-submodular functions, in Proceedings of ISCO 2012, Lecture Notes in Comput. Sci. 7422, Springer, Heidelberg, 2012, pp. 451--462], of extreme points of the $k$-submodular polyhedron and make it a correct one by fixing a flaw therein.

Given a system $(V,f,d)$ on a finite set V consisting of two set functions $f:2^V\to\mathbb{R}$ and $d:2^V\to\mathbb{R}$, we consider the problem of finding a set $R\subseteq V$ of minimum cardinality such that $f(X)\ge d(X)$ for all $X\subseteq V-R$, where the problem can be regarded as a natural generalization of the source location problems and the external network problems in (undirected) graphs and hypergraphs. We give a structural characterization of minimal deficient sets of $(V,f,d)$ under certain conditions. We show that all such sets form a tree hypergraph if f is posimodular and d is modulotone (i.e., each nonempty subset X of V has an element $v\in X$ such that $d(Y)\ge d(X)$ for all subsets Y of X that contain v) and that, conversely, any tree hypergraph can be represented by minimal deficient sets of $(V,f,d)$ for a posimodular function f and a modulotone function d. By using this characterization, we present a polynomial-time algorithm if, in addition, f is submodular and d is given by either $d(X)=\max\{p(v)\mid v\in X\}$ for a function $p:V\to\RR_+$ or $d(X)=\max\{r(v,w)\mid v\in X,w\in V-X\}$ for a function $r:V^2\to\mathbb{R}_+$. Our result provides first polynomial-time algorithms for the source location problem in hypergraphs and the external network problems in graphs and hypergraphs. We also show that the problem is intractable, even if f is submodular and $d\equiv\mathbf{0}$.

This paper presents the first combinatorial polynomial algorithm for minimizing bisubmodular functions, extending the scaling algorithm for submodular function minimization due to Iwata, Fleischer, and Fujishige. Since the rank functions of delta-matroids are bisubmodular, the scaling algorithm naturally leads to the first combinatorial polynomial algorithm for testing membership in delta-matroid polyhedra.

This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grötschel, Lovász, and Schrijver. The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter. The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the length of the largest absolute function value. The paper also presents a strongly polynomial version in which the number of steps is bounded by a polynomial in the size of the underlying set, independent of the function values.

This paper presents the first combinatorial polynomialtime algorithm for minimizing submodular functions, answering an open question posed in 1981 by GrStschel, Love%sz, and Schrijver.The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter.The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the largest length of the function value.The paper also presents a strongly polynomial-time version that runs in time bounded by a polynomial in the size of the underlying set independent of the function value.*A part of this work is done while on leave at the Fields Institute, Toronto, Canada.Partly supported

For a family ${\cal F} \subseteq 3^E$ closed with respect to the reduced union and intersection and for a bisubmodular function $f: {\cal F}\rightarrow \mbox{\bf R}$ with $(\emptyset,\emptyset) \in \cal F$ and $f(\emptyset,\emptyset)=0$, the bisubmodular polyhedron associated with $({\cal F},f)$ is given by \[ {\rm P}_*(f)=\{x\,|\,x\in\mbox{\bf R}^E\quad \forall (X,Y)\in {\cal F}: x(X,Y)\le f(X,Y)\}, \] where $x(X,Y)=\sum_{e\in X}x(e)-\sum_{e\in Y}x(e)$. We show a min--max relation that characterizes the distance between ${\rm P}_*(f)$ and a given point $x^0$ with respect to the $l_1$ norm: for any vector $x^0\in\mbox{\bf R}^E$, \[ \left. \min\left\{\sum_{e\in E}|x(e)-x^0(e)|\, \right| \,x\in{\rm P}_*(f)\right\} =\max\{x^0(X,Y)-f(X,Y)\,|\,(X,Y)\in{\cal F}\}, \] where if f is integer valued and $x^0$ is integral, then the minimum is attained by an integral $x\in{\rm P}_*(f)$. This is in a sense equivalent to but is in a nicer symmetric form than a min--max theorem of Cunningham and Green-Krótki [Combinatorica, 11 (1991), pp. 219--230] shown to be associated with b-matching degree-sequence polyhedra and generalizes the well-known min--max theorem concerning a vector reduction of polymatroids and submodular systems. We also give an application of the theorem to a separable convex optimization problem on bisubmodular polyhedra.

Abstract The problem of updating shortest paths from all the vertices to a set of vertices when the length function is decreased was considered by S. Goto and A. Sangiovanni‐Vincentelli and a solution algorithm was presented based on the LU‐factorization of the measure matrix and a matrix inversion formula. The present paper shows that the problem can be solved by means of the Dijkstra method in a running time of the same order as Goto and Sangiovanni‐Vincentelli's algorithm, assuming a smaller amount of initial data than theirs, i.e., we do not need the LU‐factorization of the measure matrix.

The optimal control problem for unreliable dynamic systems with random failure was investigated by Murthy [1]. This note shows that the controller algorithm proposed in [1] is suboptimal.