Arrow Research search

Author name cluster

Satoru Iwata 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers
1 author row

Possible papers

14

SODA Conference 2020 Conference Paper

A Blossom Algorithm for Maximum Edge-Disjoint T -Paths

  • Satoru Iwata 0001
  • Yu Yokoi

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.

Details

STOC Conference 2017 Conference Paper

A weighted linear matroid parity algorithm

  • Satoru Iwata 0001
  • Yusuke Kobayashi 0001

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.

Details

SODA Conference 2016 Conference Paper

Improved Approximation Algorithms for k -Submodular Function Maximization

  • Satoru Iwata 0001
  • Shin-ichi Tanigawa
  • Yuichi Yoshida

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 /(2 k – 1)-approximation algorithm while for any ∊ > 0 a (( k + 1)/2 k + ∊ )-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.

Details

SODA Conference 2009 Conference Paper

A simple combinatorial algorithm for submodular function minimization

  • Satoru Iwata 0001
  • James B. Orlin

This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O ( n 6 EO 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 (( n 4 EO + n 5 ) log nM ) time. The strongly polynomial version of this faster algorithm runs in O (( n 5 EO + n 6 ) 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.

Details

SODA Conference 2009 Conference Paper

Approximating submodular functions everywhere

  • Michel X. Goemans
  • Nicholas J. A. Harvey
  • Satoru Iwata 0001
  • Vahab Mirrokni

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.

Details

FOCS Conference 2009 Conference Paper

Submodular Function Minimization under Covering Constraints

  • Satoru Iwata 0001
  • Kiyohito Nagano

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.

Details
v2026.09.13