Abstract. Let [Formula: see text] be a multigraph with a set [Formula: see text] of terminals. A path in [Formula: see text] is called a [Formula: see text]-path if its ends are distinct vertices in [Formula: see text] and no internal vertices belong to [Formula: see text]. In 1978, Mader showed a characterization of the maximum number of edge-disjoint [Formula: see text]-paths. In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjoint [Formula: see text]-paths. The algorithm adopts an augmenting path approach. More specifically, we utilize a new concept of short augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjoint [Formula: see text]-paths. To design a search procedure for a short augmenting walk, we introduce blossoms analogously to the matching algorithm of Edmonds [ Canad. J. Math., 17, 1965, pp. 449–467]. When the search procedure terminates without finding a short augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjoint [Formula: see text]-paths. From this certificate, one can obtain the Edmonds–Gallai type decomposition introduced by Sebő and Szegő [ Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization, LNCS 3064, Springer, Berlin, 2004, pp. 256–270]. The algorithm runs in [Formula: see text] time, which is much faster than the best known deterministic algorithm based on a reduction to linear matroid parity. We also present a strongly polynomial algorithm for the maximum integer free multiflow problem, which asks for a nonnegative integer combination of [Formula: see text]-paths maximizing the sum of the coefficients subject to capacity constraints on the edges.

The maximum a posteriori (MAP) inference for determinantal point processes (DPPs) is crucial for selecting diverse items in many machine learning applications. Although DPP MAP inference is NP-hard, the greedy algorithm often finds high-quality solutions, and many researchers have studied its efficient implementation. One classical and practical method is the lazy greedy algorithm, which is applicable to general submodular function maximization, while a recent fast greedy algorithm based on the Cholesky factorization is more efficient for DPP MAP inference. This paper presents how to combine the ideas of lazy'' andfast'', which have been considered incompatible in the literature. Our lazy and fast greedy algorithm achieves almost the same time complexity as the current best one and runs faster in practice. The idea of ``lazy + fast'' is extendable to other greedy-type algorithms. We also give a fast version of the double greedy algorithm for unconstrained DPP MAP inference. Experiments validate the effectiveness of our acceleration ideas.

The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Nevertheless, Lovász [ Acta Sci. Math., 42 (1980), pp. 121--131] showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem. In this paper, we present a combinatorial, deterministic, polynomial-time algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann [ Combinatorica, 6 (1986), pp. 123--150] for the unweighted problem.

Let G = (V, E) be a multigraph with a set T ⊆ V of terminals. A path in G is called a T-path if its ends are distinct vertices in T and no internal vertices belong to T. In 1978, Mader showed a characterization of the maximum number of edge-disjoint T-paths. The original proof was not constructive, and hence it did not suggest an efficient algorithm. In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjoint T-paths. The algorithm adopts an augmenting path approach. More specifically, we introduce a novel concept of augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjoint T-paths. To design a search procedure for an augmenting walk, we introduce blossoms analogously to the blossom algorithm of Edmonds (1965) for the matching problem, while it is neither a special case nor a generalization of the present problem. When the search procedure terminates without finding an augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjoint T-paths. Thus the correctness argument of the algorithm serves as an alternative direct proof of Mader's theorem on edge-disjoint T-paths. The algorithm runs in O(|V| • |E|2) time, which is much faster than the best known deterministic algorithm based on a reduction to the linear matroid parity problem.

Differential-algebraic equations (DAEs) are widely used for the modeling of dynamical systems. The difficulty in numerically solving a DAE is measured by its differentiation index. For highly accurate simulation of dynamical systems, it is important to convert high-index DAEs into low-index DAEs. Most of the existing simulation software packages for dynamical systems are equipped with an index-reduction algorithm given by Mattsson and Söderlind. Unfortunately, this algorithm fails if there are numerical cancellations. These numerical cancellations are often caused by accurate constants in structural equations. Distinguishing those accurate constants from generic parameters that represent physical quantities, Murota and Iri introduced the notion of a mixed matrix as a mathematical tool for faithful model description in a structural approach to systems analysis. For DAEs described with the use of mixed matrices, efficient algorithms to compute the index have been developed by exploiting matroid theory. This article presents an index-reduction algorithm for linear DAEs whose coefficient matrices are mixed matrices, i.e., linear DAEs containing physical quantities as parameters. Our algorithm detects numerical cancellations between accurate constants and transforms a DAE into an equivalent DAE to which Mattsson–Söderlind’s index-reduction algorithm is applicable. Our algorithm is based on the combinatorial relaxation approach, which is a framework to solve a linear algebraic problem by iteratively relaxing it into an efficiently solvable combinatorial optimization problem. The algorithm does not rely on symbolic manipulations but on fast combinatorial algorithms on graphs and matroids. Our algorithm is proved to work for any linear DAEs whose coefficient matrices are mixed matrices. Furthermore, we provide an improved algorithm under an assumption based on dimensional analysis of dynamical systems. Through numerical experiments, it is confirmed that our algorithms run sufficiently fast for large-scale DAEs and output DAEs such that physical meanings of coefficients are easy to interpret. Our algorithms can also be applied to nonlinear DAEs by regarding nonlinear terms as parameters.

The Dulmage--Mendelsohn decomposition (or the DM-decomposition) gives a unique partition of the vertex set of a bipartite graph reflecting the structure of all the maximum matchings therein. A bipartite graph is said to be DM-irreducible if its DM-decomposition consists of a single component. In this paper, we focus on the problem of making a given bipartite graph DM-irreducible by adding edges. When the input bipartite graph is balanced (i.e., both sides have the same number of vertices) and has a perfect matching, this problem is equivalent to making a directed graph strongly connected by adding edges, for which the minimum number of additional edges was characterized by Eswaran and Tarjan [ SIAM J. Comput., 5 (1976), pp. 653--665]. We give a general solution to this problem, which is divided into three parts. We first show that our problem can be formulated as a special case of a general framework of covering supermodular functions, which was introduced by Frank and Jordán [ J. Combin. Theory Ser. B, 65 (1995), pp. 73--110] to investigate the directed connectivity augmentation problem. Second, when the input graph is not balanced, the problem is solved via matroid intersection. This result can be extended to the minimum cost version in which the addition of an edge gives rise to an individual cost. Third, for balanced input graphs, we devise a combinatorial algorithm that finds a minimum number of additional edges to attain the DM-irreducibility, while the minimum cost version of this problem is NP-hard. These results also lead to min-max characterizations of the minimum number, which generalize the result of Eswaran and Tarjan.

The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Nevertheless, Lovasz (1978) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem. This talk presents a recently developed polynomial-time algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann (1986) for the unweighted problem.

The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Lovász (1980) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem.

This paper presents a polynomial-time 1/2-approximation algorithm for maximizing nonnegative k-submodular functions. This improves upon the previous max{1/3, 1/(1 + a)}-approximation by Ward and Živný [18], where a = . We also show that for monotone k-submodular functions there is a polynomial-time k/(2k – 1)-approximation algorithm while for any ∊ > 0 a ((k + 1)/2k + ∊)-approximation algorithm for maximizing monotone k-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skewbisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

The stable matching model of Gale and Shapley (1962) has been generalized in various directions such as matroid kernels due to Fleiner (2001) and stable allocations in bipartite networks due to Baïou and Balinski (2002). Unifying these generalizations, we introduce the concept of stable allocations in polymatroid intersection. Our framework includes both integer- and real-variable versions. The integer-variable version corresponds to a special case of the discrete-concave function model due to Eguchi, Fujishige, and Tamura (2003), who established the existence of a stable allocation by showing that a simple extension of the deferred acceptance algorithm of Gale and Shapley finds a stable allocation in pseudo-polynomial time. It has been open to develop a polynomial-time algorithm even for our special case. In this paper, we present the first strongly polynomial algorithm for finding a stable allocation in polymatroid intersection. To achieve this, we utilize the augmenting path technique for polymatroid intersection. In each iteration, the algorithm searches for an augmenting path by simulating a chain of proposes and rejects in the deferred acceptance algorithm. The running time of our algorithm is O(n3γ), where n and γ respectively denote the cardinality of the ground set and the time for computing the saturation and exchange capacities. This is as fast as the best known algorithm for the polymatroid intersection problem.

The Fisher discriminant analysis (FDA) is a common technique for binary classification. A parametrized extension, which we call the extended FDA, has been introduced from the viewpoint of robust optimization. In this work, we first give a new probabilistic interpretation of the extended FDA. We then develop algorithms for solving an optimization problem that arises from the extended FDA: computing the distance between a point and the surface of an ellipsoid. We solve this problem via the KKT points, which we show are obtained by solving a generalized eigenvalue problem. We speed up the algorithm by taking advantage of the matrix structure and proving that a globally optimal solution is a KKT point with the smallest Lagrange multiplier, which can be computed efficiently as the leftmost eigenvalue. Numerical experiments illustrate the efficiency and effectiveness of the extended FDA model combined with our algorithm.

In this paper we are interested in algorithms for finding $2$-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. Since a Hamilton cycle is a 2-factor covering all edge-cuts, imposing the constraint of covering those edge-cuts makes the obtained $2$-factor closer to a Hamilton cycle. We present an algorithm for finding a minimum-weight $2$-factor covering all the $3$-edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such 2-factors and that of perfect matchings intersecting all the 3-edge cuts in exactly one edge. We further give an algorithm for finding a 2-factor covering all the $3$- and $4$-edge cuts in bridgeless cubic graphs. Both of these algorithms run in ${\rm O}(n\sp{3})$ time, where $n$ is the number of vertices. As an application of the latter algorithm, we design a 6/5-approximation algorithm for finding a minimum 2-edge-connected spanning subgraph in 3-edge-connected cubic graphs, which improves upon the previous best ratio of 5/4. The algorithm begins with finding a 2-factor covering all 3- and 4-edge cuts, which is the bottleneck in terms of complexity, and thus it has running time ${\rm O}(n\sp{3})$. We then improve this time complexity to ${\rm O}(n\sp{2} \log\sp{4}n)$ by relaxing the condition of the initial $2$-factor and elaborating on the subsequent processes.

A number of objective functions in clustering problems can be described with submodular functions. In this paper, we introduce the minimum average cost criterion, and show that the theory of intersecting submodular functions can be used for clustering with submodular objective functions. The proposed algorithm does not require the number of clusters in advance, and it will be determined by the property of a given set of data points. The minimum average cost clustering problem is parameterized with a real variable, and surprisingly, we show that all information about optimal clusterings for all parameters can be computed in polynomial time in total. Additionally, we evaluate the performance of the proposed algorithm through computational experiments.

This paper addresses the problems of minimizing nonnegative submodular functions under covering constraints, which generalize the vertex cover, edge cover, and set cover problems. We give approximation algorithms for these problems exploiting the discrete convexity of submodular functions. We first present a rounding 2-approximation algorithm for the submodular vertex cover problem based on the half-integrality of the continuous relaxation problem, and show that the rounding algorithm can be performed by one application of submodular function minimization on a ring family. We also show that a rounding algorithm and a primal-dual algorithm for the submodular cost set cover problem are both constant factor approximation algorithms if the maximum frequency is fixed. In addition, we give an essentially tight lower bound on the approximability of the submodular edge cover problem.

Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using only polynomially many queries to the oracle, e.g., exact minimization or approximate maximization. In this paper, we consider the problem of approximating a non-negative, monotone, submodular function f on a ground set of size n everywhere, after only poly(n) oracle queries. Our main result is a deterministic algorithm that makes poly(n) oracle queries and derives a function such that, for every set S, (S) approximates f(S) within a factor α(n), where for rank functions of matroids and for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids. Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than , even for rank functions of a matroid.

This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n6EO log nM) time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function evaluation. The algorithm can be improved to run in O((n4EO + n5) log nM) time. The strongly polynomial version of this faster algorithm runs in O((n5EO + n6) log n) time for real valued general submodular functions. These are comparable to the best known running time bounds for submodular function minimization. The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method.

A mixed polynomial matrix is a polynomial matrix which has two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. This paper presents an algorithm for computing the degrees of all cofactors simultaneously in a regular mixed polynomial matrix. The algorithm is based on the valuated matroid intersection and all pair shortest paths. The technique is also used for improving the running time of the algorithm for minimizing the index of the differential-algebraic equation in the hybrid analysis for circuit simulation.

This paper deals with the independent even factor problem. For odd-cycle-symmetric digraphs, in which each arc in any odd dicycle has the reverse arc, a min-max formula is established as a common generalization of the Tutte–Berge formula for matchings and the min-max formula of Edmonds [Submodular functions, matroids, and certain polyhedra, in Combinatorial Structures and Their Applications, R. Guy et al., eds., Gordon and Breach, New York, 1970, pp. 69–87] for matroid intersection. We devise a combinatorial efficient algorithm to find a maximum independent even factor in an odd-cycle-symmetric digraph accompanied by general matroids, which commonly extends two of the alternating-path-type algorithms, the even factor algorithm of Pap [Math. Program., 110 (2007), pp. 57–69], and the matroid intersection algorithms. This algorithm gives a proof of the min-max formula and contains a new operation on matroids, which corresponds to shrinking factor-critical components in the matching algorithm of Edmonds [Canad. J. Math., 17 (1965), pp. 449–467]. The running time of the algorithm is $\mathrm{O}(n^4 Q)$, where n is the number of vertices and Q is the time for an independence test. The algorithm also gives a common generalization of the Edmonds–Gallai decomposition for matchings and the principal partition for matroid intersection.

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 new strongly polynomial cut canceling algorithm for minimum cost submodular flow. The algorithm is a generalization of our similar cut canceling algorithm for ordinary min-cost flow. The algorithm scales a relaxed optimality parameter and creates a second, inner relaxation that is a kind of submodular max flow problem. The outer relaxation uses a novel technique for relaxing the submodular constraints that allows our previous proof techniques to work. The algorithm uses the min cuts from the max flow subproblem as the relaxed most positive cuts it chooses to cancel. We show that this algorithm needs to cancel only ${\mathrm O}(n^3)$ cuts per scaling phase, where n is the number of nodes. Furthermore, we show how to slightly modify this algorithm to get a strongly polynomial running time. Finally, we briefly show how to extend this algorithm to the separable convex cost case and that the same technique can be used to construct a polynomial time maximum mean cut canceling algorithm for submodular flow.

Abstract In the game theory approach to cost allocation, the main computational issue is an algorithm for finding solutions such as the Shapley value and the nucleolus. In this article, we consider the problem of allocating the maintenance cost of a tree network that connects the supply source at the root to the users at the leaves. We show that the core of the game can be expressed in terms of network flows. Based on this observation, we present O(n log n) algorithms for computing the nucleolus and the egalitarian allocation. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 297–301 2004

Combinatorial strongly polynomial algorithms for minimizing submodular functions have been developed by Iwata, Fleischer, and Fujishige (IFF) and by Schrijver. The IFF algorithm employs a scaling scheme for submodular functions, whereas Schrijver's algorithm achieves strongly polynomial bound with the aid of distance labeling. Subsequently, Fleischer and Iwata have described a push/relabel version of Schrijver's algorithm to improve its time complexity. This paper combines the scaling scheme with the push/relabel framework to yield a faster combinatorial algorithm for submodular function minimization. The resulting algorithm improves over the previously best known bound by essentially a linear factor in the size of the underlying ground set.

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.

Very recently, two groups of researchers independently developed the first combinatorial, strongly polynomial-time algorithms for submodular function minimization (Iwata, Fleischer, Fujishige; and Schrijver).In this paper, we improve on these algorithms and show that the ideas generated in the design of these algorithms are helpful in other contexts.This work demonstrates one use of combinatorial algorithms for submodular function minimization.In particular we accomplish three things.First, we improve the complexity of Schrijver's algorithm by designing a push-relabel algorithm for submodular function minimization (SFM).Second, we exploit the common structure shared between submodular function minimization and maximum submodular flow to design the first algorithm for maximum submodular flow that does not depend on an oracle for SFM.The overall time complexity is the same as for SFM.Finally, we design the first algorithms for minimum cost submodular flow that do not depend on an oracle for SFM, using the framework of submodular function minimization of Iwata, Fleischer, Fujishige.We show that optimal dual solutions can be computed in the same time as SFM, and that optimal primal solutions can thus be obtained with one additional maximum submodular flow computation.We give both weakly and strongly polynomial versions.* Part of this work done while on leave at the Fields Institute, Toronto, Canada.

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

A matrix $A = \begin{pmatrix} Q \\ T \end{pmatrix}$ is called a layered mixed matrix (LM-matrix) if the set of nonzero entries of T is algebraically independent over the field to which the entries of Q belong. This concept has been proposed as a mathematical tool for describing discrete physical/engineering systems. It is known that there uniquely exists a finest block-triangularization of an LM-matrix, which is called the combinatorial canonical form (CCF). In this paper, associated with an LM-matrix we introduce a new submodular function q characterizing its rank. This submodular function q is defined on a modular lattice. It will be shown that the principal structure of q gives the coarsest decomposition of the row side that is finer than any decomposition induced by the CCF of the submatrix consisting of a base of the column vectors of A. This gives a best possible bound on the extent to which the whole system can be decomposed by a suitable choice of design variables.