SatoruIwata

Archive of posts with tag 'SatoruIwata'

  • Satoru Iwata, Approximating Max-Min Weighted T-join
    Approximating Max-Min Weighted T-join
    Satoru Iwata
    RIMS, Kyoto University, Kyoto, Japan
    2011/11/11 Fri 4PM-5PM
    Given an even subset T of the vertices of an undirected graph, a T-join is a subgraph in which the subset of vertices with odd degree is exactly T. Given edge weights, the weighted T-join problem is to find a T-join of minimum weight. With nonnegative edge weights, the problem can be reduced to finding a minimum weight perfect matching on the metric completion of the vertices in T.
    Given an undirected graph with nonnegative edge weights but no specific T, the Max-Min Weighted T-join problem is to find an even cardinality vertex subset T such that the minimum weight T-join for this set is maximum. The unweighted case of the problem when all weights are either unit or infinity has been well characterized by a decomposition of the underlying graph into factor critical and matching-covered bipartite subgraphs (Frank1993). We consider the weighted version which is NP-hard even on a cycle. After showing a simple exact solution on trees, we present a 2/3-approximation algorithm for the general case. Our algorithm is based on a natural cut packing upper bound obtained using an LP relaxation and uncrossing, and relating it to the T-join problem using duality.
    This is a joint work with R. Ravi.
    Tags:

  • (Colloquium) Satoru Iwata, Submodular Optimization and Approximation Algorithms
    Submodular Optimization and Approximation Algorithms
    Satoru Iwata
    RIMS, Kyoto University, Kyoto, Japan
    2011/11/10 Thu 4PM-5PM
    Submodular functions are discrete analogues of convex functions. Examples include cut capacity functions, matroid rank functions, and entropy functions. Submodular functions can be minimized in polynomial time, which provides a fairly general framework of efficiently solvable combinatorial optimization problems. In contrast, the maximization problems are NP-hard and several approximation algorithms have been developed so far.
    In this talk, I will review the above results in submodular optimization and present recent approximation algorithms for combinatorial optimization problems described in terms of submodular functions.
    Tags:

Monthly Archives