Source author record

Satoru Iwata

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory Discrete Mathematics Machine Learning math.CO math.OC

Catalog footprint

Research overview

4works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Improved Approximation Algorithms for k-Submodular Function Maximization

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ý~(SODA'14), where $a=\max\{1, \sqrt{(k-1)/4}\}$ . We also show that for monotone $k$ -submodular functions there is a polynomial-time $k/(2k-1)$ -approximation algorithm while for any $\varepsilon>0$ a $((k+1)/2k+\varepsilon)$ -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 skew-bisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

preprint2014arXiv

Extended Formulations for Sparsity Matroids

We show the existence of a polynomial-size extended formulation for the base polytope of a $(k,\ell)$ -sparsity matroid. For an undirected graph $G=(V,E)$ , the size of the formulation is $O(|V||E|)$ when $k \geq \ell$ and $O(|V|^2 |E|)$ when $k \leq \ell$ . To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol.

preprint2014arXiv

Graph-TSP from Steiner Cycles

We present an approach for the traveling salesman problem with graph metric based on Steiner cycles. A Steiner cycle is a cycle that is required to contain some specified subset of vertices. For a graph $G$ , if we can find a spanning tree $T$ and a simple cycle that contains the vertices with odd-degree in $T$ , then we show how to combine the classic "double spanning tree" algorithm with Christofides' algorithm to obtain a TSP tour of length at most $\frac{4n}{3}$ . We use this approach to show that a graph containing a Hamiltonian path has a TSP tour of length at most $4n/3$ . Since a Hamiltonian path is a spanning tree with two leaves, this motivates the question of whether or not a graph containing a spanning tree with few leaves has a short TSP tour. The recent techniques of Mömke and Svensson imply that a graph containing a depth-first-search tree with $k$ leaves has a TSP tour of length $4n/3 + O(k)$ . Using our approach, we can show that a $2(k-1)$ -vertex connected graph that contains a spanning tree with at most $k$ leaves has a TSP tour of length $4n/3$ . We also explore other conditions under which our approach results in a short tour.

preprint2011arXiv

Learning Valuation Functions

In this paper we study the approximate learnability of valuations commonly used throughout economics and game theory for the quantitative encoding of agent preferences. We provide upper and lower bounds regarding the learnability of important subclasses of valuation functions that express no-complementarities. Our main results concern their approximate learnability in the distributional learning (PAC-style) setting. We provide nearly tight lower and upper bounds of $\tildeΘ(n^{1/2})$ on the approximation factor for learning XOS and subadditive valuations, both widely studied superclasses of submodular valuations. Interestingly, we show that the $\tildeΩ(n^{1/2})$ lower bound can be circumvented for XOS functions of polynomial complexity; we provide an algorithm for learning the class of XOS valuations with a representation of polynomial size achieving an $O(n^{\eps})$ approximation factor in time $O(n^{1/\eps})$ for any $\eps > 0$. This highlights the importance of considering the complexity of the target function for polynomial time learning. We also provide new learning results for interesting subclasses of submodular functions. Our upper bounds for distributional learning leverage novel structural results for all these valuation classes. We show that many of these results provide new learnability results in the Goemans et al. model (SODA 2009) of approximate learning everywhere via value queries. We also introduce a new model that is more realistic in economic settings, in which the learner can set prices and observe purchase decisions at these prices rather than observing the valuation function directly. In this model, most of our upper bounds continue to hold despite the fact that the learner receives less information (both for learning in the distributional setting and with value queries), while our lower bounds naturally extend.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.