Naonori Kakimura

AAMAS Conference 2026 Conference Paper

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization

• Philip Cervenjak
• Junhao Gan
• Naonori Kakimura
• Seeun William Umboh
• Anthony Wirth

Connected Submodular Maximization (CSM) is a graph problem with important applications to wireless network deployment, path planning, epidemic outbreaks, and cancer genome studies. In CSM, we are given a graph 𝐺, a non-negative monotone submodular function 𝑓 on subsets of the vertex set of 𝐺, and an integer 𝑘. The goal is to select a tree in 𝐺, with 𝑘 edges, whose vertex set maximizes 𝑓. We also study the more general Directed and Directed Rooted variants of CSM (DCSM and DRCSM respectively). In both variants, 𝐺 is directed and the solution must be an out-tree in 𝐺, with 𝑘 edges, whose vertex set maximizes 𝑓; DRCSM further specifies a vertex to be the root of the selected out-tree. For CSM, several previous works have proposed polynomial time approximation algorithms; the state-of-the-art polynomial time algorithm achieves a Ω( 1 √ 𝑘 )-approximation. We can also parameterize the approximation factor by the radius of the optimal solution, denoted by 𝑟; the state-of-the-art polynomial time algorithm achieves a Ω(1 𝑟 )-approximation. In this paper, we improve on the state-of-the-art approximation factor for CSM with respect to 𝑟 as well as 𝑘, noting that 𝑟 ≤ 𝑘. We propose a polynomial time framework that, for (Directed) CSM, achieves a Ω(𝜀3 𝑟𝜀 )-approximation for every constant 𝜀 ∈ (0, 1]. For DRCSM, our framework achieves a Ω(𝛿𝜀3 𝑟𝜀 )-approximation that violates the size constraint by at most a factor of 1 + 𝛿 for every 𝛿 ∈ [1 𝑘, 1]. A key component of our framework is GreedyRadius, an algorithm for DRCSM that outputs a bicriteria approximation, i. e. , an approximate solution that violates the size constraint by at most some factor. GreedyRadius takes an algorithm with a bicriteria approximation factor in terms of𝑘 and outputs a solution This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), C. Amato, L. Dennis, V. Mascardi, J. Thangarajah (eds.), May 25 – 29, 2026, Paphos, Cyprus. © 2026 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). https: //doi. org/10. 65109/IPZQ7320 with the same bicriteria approximation factor (up to constants) in termsof𝑟. Moreover, touseasasubroutineforDRCSM, wepropose the algorithm RecApprox-𝑑, which achieves a 1 𝑑+1-approximation that violates the size constraint by at most a factor of (𝑑 + 1)2𝑘 1 𝑑. RecApprox-𝑑 uses a recursive greedy strategy, with𝑑 denoting the number of levels of recursion used. This enables the dependence on 𝜀 in the approximation factors of our overall framework.

TCS Journal 2025 Journal Article

Deterministic primal-dual algorithms for online k-way matching with delays

• Naonori Kakimura
• Tomohiro Nakayoshi

In this paper, we study the Min-cost Perfect k-way Matching with Delays (k-MPMD), recently introduced by Melnyk et al. In the problem, m requests arrive one-by-one over time in a metric space. At any time, we can irrevocably make a group of k requests who arrived so far, that incurs the distance cost among the k requests in addition to the sum of the waiting cost for the k requests. The goal is to partition all the requests into groups of k requests, minimizing the total cost. The problem is a generalization of the min-cost perfect matching with delays (corresponding to 2-MPMD). It is known that no online algorithm for k-MPMD can achieve a bounded competitive ratio in general, where the competitive ratio is the worst-case ratio between its performance and the offline optimal value. On the other hand, k-MPMD is known to admit a randomized online algorithm with competitive ratio O ( k 5 log ⁡ n ) for a certain class of k-point metrics called the H-metric, where n is the size of the metric space. In this paper, we propose a deterministic online algorithm with a competitive ratio of O ( m k 2 ) for the k-MPMD in H-metric space. Furthermore, we show that the competitive ratio can be improved to O ( m + k 2 ) if the metric is given as a diameter on a line.

AAAI Conference 2024 Conference Paper

New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem

• Koji Ichikawa
• Shinji Ito
• Daisuke Hatano
• Hanna Sumita
• Takuro Fukunaga
• Naonori Kakimura
• Ken-ichi Kawarabayashi

We consider the sparse contextual bandit problem where arm feature affects reward through the inner product of sparse parameters. Recent studies have developed sparsity-agnostic algorithms based on the greedy arm selection policy. However, the analysis of these algorithms requires strong assumptions on the arm feature distribution to ensure that the greedily selected samples are sufficiently diverse; One of the most common assumptions, relaxed symmetry, imposes approximate origin-symmetry on the distribution, which cannot allow distributions that has origin-asymmetric support. In this paper, we show that the greedy algorithm is applicable to a wider range of the arm feature distributions from two aspects. Firstly, we show that a mixture distribution that has a greedy-applicable component is also greedy-applicable. Second, we propose new distribution classes, related to Gaussian mixture, discrete, and radial distribution, for which the sample diversity is guaranteed. The proposed classes can describe distributions with origin-asymmetric support and, in conjunction with the first claim, provide theoretical guarantees of the greedy policy for a very wide range of the arm feature distributions.

TCS Journal 2024 Journal Article

Randomized counter-based algorithms for frequency estimation over data streams in O ( log ⁡ log ⁡ N ) space

• Naonori Kakimura
• Riku Nitta

This note studies the problem of estimating frequencies of items over data streams. We propose a simple streaming algorithm for the problem in small space complexity. Our algorithm is a counter-based algorithm with the aid of probabilistic counting. We show that our algorithm with k counters computes, with probability at least 1 − δ, the estimation with relative error at most ( 1 + ε ) N / k, taking O ( k log ⁡ log ⁡ N k + k log ⁡ ( ε − 1 δ − 1 k ) + k log ⁡ ℓ ) space in expectation, where N is the total number of items and ℓ is the number of different items.

NeurIPS Conference 2023 Conference Paper

Bandit Task Assignment with Unknown Processing Time

• Shinji Ito
• Daisuke Hatano
• Hanna Sumita
• Kei Takemura
• Takuro Fukunaga
• Naonori Kakimura
• Ken-ichi Kawarabayashi

This study considers a novel problem setting, referred to as \textit{bandit task assignment}, that incorporates the processing time of each task in the bandit setting. In this problem setting, a player sequentially chooses a set of tasks to start so that the set of processing tasks satisfies a given combinatorial constraint. The reward and processing time for each task follow unknown distributions, values of which are revealed only after the task has been completed. The problem generalizes the stochastic combinatorial semi-bandit problem and the budget-constrained bandit problem. For this problem setting, we propose an algorithm based on upper confidence bounds~(UCB) combined with a phased-update approach. The proposed algorithm admits a gap-dependent regret upper bound of $O(MN(1/\Delta){\log T})$ and a gap-free regret upper bound of $\tilde{O}( \sqrt{MNT} )$, where $N$ is the number of the tasks, $M$ is the maximum number of tasks run at the same time, $T$ is the time horizon, and $\Delta$ is the gap between expected per-round rewards of the optimal and best suboptimal sets of tasks. These regret bounds nearly match lower bounds.

TCS Journal 2023 Journal Article

On reachable assignments under dichotomous preferences

• Takehiro Ito
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yuta Nozaki
• Yoshio Okamoto
• Kenta Ozeki

We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents. In particular, we consider the situation where each agent has a dichotomous preference over the items, that is, each agent evaluates each item as acceptable or unacceptable. Furthermore, we assume that communication between agents is limited, and the relationship is represented by an undirected graph. Then, a pair of agents can exchange their items only if they are connected by an edge and the involved items are acceptable. We prove that this problem is PSPACE -complete even when the communication graph is complete (that is, every pair of agents can exchange their items), and this problem can be solved in polynomial time if an input graph is a tree.

SODA Conference 2022 Conference Paper

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

• Takehiro Ito
• Yuni Iwamasa
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi 0001
• Shun-ichi Maezawa
• Yuta Nozaki
• Yoshio Okamoto

We initiate the study of k -edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2 k -edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k -edge-connected. This yields an “edge-flip based” new proof of Nash-Williams' theorem: an undirected graph G has a k -edge-connected orientation if and only if G is 2 k -edge-connected. As another consequence of the theorem, we prove that the edge-flip graph of k -edge-connected orientations of an undirected graph G is connected if G is (2 k + 2)-edge-connected. This has been known to be true only when k = 1.

AAAI Conference 2022 Conference Paper

Online Task Assignment Problems with Reusable Resources

• Hanna Sumita
• Shinji Ito
• Kei Takemura
• Daisuke Hatano
• Takuro Fukunaga
• Naonori Kakimura
• Ken-ichi Kawarabayashi

We study online task assignment problem with reusable resources, motivated by practical applications such as ridesharing, crowdsourcing and job hiring. In the problem, we are given a set of offline vertices (agents), and, at each time, an online vertex (task) arrives randomly according to a known time-dependent distribution. Upon arrival, we assign the task to agents immediately and irrevocably. The goal of the problem is to maximize the expected total profit produced by completed tasks. The key features of our problem are (1) an agent is reusable, i. e. , an agent comes back to the market after completing the assigned task, (2) an agent may reject the assigned task to stay the market, and (3) a task may accommodate multiple agents. The setting generalizes that of existing work in which an online task is assigned to one agent under (1). In this paper, we propose an online algorithm that is 1/2competitive for the above setting, which is tight. Moreover, when each agent can reject assigned tasks at most ∆ times, the algorithm is shown to have the competitive ratio ∆/(3∆ − 1) ≥ 1/3. We also evaluate our proposed algorithm with numerical experiments.

AAAI Conference 2022 Conference Paper

Reforming an Envy-Free Matching

• Takehiro Ito
• Yuni Iwamasa
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yuta Nozaki
• Yoshio Okamoto
• Kenta Ozeki

We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

AAAI Conference 2021 Conference Paper

Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions

• Kei Takemura
• Shinji Ito
• Daisuke Hatano
• Hanna Sumita
• Takuro Fukunaga
• Naonori Kakimura
• Ken-ichi Kawarabayashi

The contextual combinatorial semi-bandit problem with linear payoff functions is a decision-making problem in which a learner chooses a set of arms with the feature vectors in each round under given constraints so as to maximize the sum of rewards of arms. Several existing algorithms have regret bounds that are optimal with respect to the number of rounds T. However, there is a gap of Õ(max( √ d, √ k)) between the current best upper and lower bounds, where d is the dimension of the feature vectors, k is the number of the chosen arms in a round, and Õ(·) ignores the logarithmic factors. The dependence of k and d is of practical importance because k may be larger than T in real-world applications such as recommender systems. In this paper, we fill the gap by improving the upper and lower bounds. More precisely, we show that the C2 UCB algorithm proposed by Qin, Chen, and Zhu (2014) has the optimal regret bound Õ(d √ kT + dk) for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C2 UCB algorithm and demonstrate that it enjoys the optimal regret bound for a more general problem that can take into account other objectives simultaneously. We also show that our technique would be applicable to related problems. Numerical experiments support our theoretical results and considerations.

TCS Journal 2020 Journal Article

Complexity of the multi-service center problem

• Takehiro Ito
• Naonori Kakimura
• Yusuke Kobayashi

The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars.

NeurIPS Conference 2020 Conference Paper

Delay and Cooperation in Nonstochastic Linear Bandits

• Shinji Ito
• Daisuke Hatano
• Hanna Sumita
• Kei Takemura
• Takuro Fukunaga
• Naonori Kakimura
• Ken-ichi Kawarabayashi

This paper offers a nearly optimal algorithm for online linear optimization with delayed bandit feedback. Online linear optimization with bandit feedback, or nonstochastic linear bandits, provides a generic framework for sequential decision-making problems with limited information. This framework, however, assumes that feedback can be observed just after choosing the action, and, hence, does not apply directly to many practical applications, in which the feedback can often only be obtained after a while. To cope with such situations, we consider problem settings in which the feedback can be observed $d$ rounds after the choice of an action, and propose an algorithm for which the expected regret is $\tilde{O}( \sqrt{m (m + d) T} )$, ignoring logarithmic factors in $m$ and $T$, where $m$ and $T$ denote the dimensionality of the action set and the number of rounds, respectively. This algorithm achieves nearly optimal performance, as we are able to show that arbitrary algorithms suffer the regret of $\Omega(\sqrt{m (m+d) T})$ in the worst case. To develop the algorithm, we introduce a technique we refer to as \textit{distribution truncation}, which plays an essential role in bounding the regret. We also apply our approach to cooperative bandits, as studied by Cesa-Bianchi et al. [17] and Bar-On and Mansour [12], and extend their results to the linear bandits setting.

NeurIPS Conference 2019 Conference Paper

Improved Regret Bounds for Bandit Combinatorial Optimization

• Shinji Ito
• Daisuke Hatano
• Hanna Sumita
• Kei Takemura
• Takuro Fukunaga
• Naonori Kakimura
• Ken-ichi Kawarabayashi

\textit{Bandit combinatorial optimization} is a bandit framework in which a player chooses an action within a given finite set $\mathcal{A} \subseteq \{ 0, 1 \}^d$ and incurs a loss that is the inner product of the chosen action and an unobservable loss vector in $\mathbb{R} ^ d$ in each round. In this paper, we aim to reveal the property, which makes the bandit combinatorial optimization hard. Recently, Cohen et al. ~\citep{cohen2017tight} obtained a lower bound $\Omega(\sqrt{d k^3 T / \log T})$ of the regret, where $k$ is the maximum $\ell_1$-norm of action vectors, and $T$ is the number of rounds. This lower bound was achieved by considering a continuous strongly-correlated distribution of losses. Our main contribution is that we managed to improve this bound by $\Omega( \sqrt{d k ^3 T} )$ through applying a factor of $\sqrt{\log T}$, which can be done by means of strongly-correlated losses with \textit{binary} values. The bound derives better regret bounds for three specific examples of the bandit combinatorial optimization: the multitask bandit, the bandit ranking and the multiple-play bandit. In particular, the bound obtained for the bandit ranking in the present study addresses an open problem raised in \citep{cohen2017tight}. In addition, we demonstrate that the problem becomes easier without considering correlations among entries of loss vectors. In fact, if each entry of loss vectors is an independent random variable, then, one can achieve a regret of $\tilde{O}(\sqrt{d k^2 T})$, which is $\sqrt{k}$ times smaller than the lower bound shown above. The observed results indicated that correlation among losses is the reason for observing a large regret.

NeurIPS Conference 2019 Conference Paper

Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback

• Shinji Ito
• Daisuke Hatano
• Hanna Sumita
• Kei Takemura
• Takuro Fukunaga
• Naonori Kakimura
• Ken-ichi Kawarabayashi

We propose computationally efficient algorithms for \textit{online linear optimization with bandit feedback}, in which a player chooses an \textit{action vector} from a given (possibly infinite) set $\mathcal{A} \subseteq \mathbb{R}^d$, and then suffers a loss that can be expressed as a linear function in action vectors. Although existing algorithms achieve an optimal regret bound of $\tilde{O}(\sqrt{T})$ for $T$ rounds (ignoring factors of $\mathrm{poly} (d, \log T)$), computationally efficient ways of implementing them have not yet been specified, in particular when $|\mathcal{A}|$ is not bounded by a polynomial size in $d$. A standard way to pursue computational efficiency is to assume that we have an efficient algorithm referred to as \textit{oracle} that solves (offline) linear optimization problems over $\mathcal{A}$. Under this assumption, the computational efficiency of a bandit algorithm can then be measured in terms of \textit{oracle complexity}, i. e. , the number of oracle calls. Our contribution is to propose algorithms that offer optimal regret bounds of $\tilde{O}(\sqrt{T})$ as well as low oracle complexity for both \textit{non-stochastic settings} and \textit{stochastic settings}. Our algorithm for non-stochastic settings has an oracle complexity of $\tilde{O}( T )$ and is the first algorithm that achieves both a regret bound of $\tilde{O}( \sqrt{T} )$ and an oracle complexity of $\tilde{O} ( \mathrm{poly} ( T ) )$, given only linear optimization oracles. Our algorithm for stochastic settings calls the oracle only $O( \mathrm{poly} (d, \log T))$ times, which is smaller than the current best oracle complexity of $O( T )$ if $T$ is sufficiently large.

MFCS Conference 2019 Conference Paper

Spectral Aspects of Symmetric Matrix Signings

• Charlie Carlson
• Karthekeyan Chandrasekaran
• Hsien-Chih Chang
• Naonori Kakimura
• Alexandra Kolla

The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of finding symmetric signings of matrices with natural spectral properties. Our results are the following: 1) We characterize matrices that have an invertible signing: a symmetric matrix has an invertible symmetric signing if and only if the support graph of the matrix contains a perfect 2-matching. Further, we present an efficient algorithm to search for an invertible symmetric signing. 2) We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing. 3) We show NP-completeness of the following problems: verifying whether a given matrix has a symmetric signing that is singular or has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs. We use combinatorial techniques in addition to classic results from matching theory.

ICML Conference 2018 Conference Paper

Causal Bandits with Propagating Inference

• Akihiro Yabe
• Daisuke Hatano
• Hanna Sumita
• Shinji Ito
• Naonori Kakimura
• Takuro Fukunaga
• Ken-ichi Kawarabayashi

Bandit is a framework for designing sequential experiments, where a learner selects an arm $A \in \mathcal{A}$ and obtains an observation corresponding to $A$ in each experiment. Theoretically, the tight regret lower-bound for the general bandit is polynomial with respect to the number of arms $|\mathcal{A}|$, and thus, to overcome this bound, the bandit problem with side-information is often considered. Recently, a bandit framework over a causal graph was introduced, where the structure of the causal graph is available as side-information and the arms are identified with interventions on the causal graph. Existing algorithms for causal bandit overcame the $\Omega(\sqrt{|\mathcal{A}|/T})$ simple-regret lower-bound; however, their algorithms work only when the interventions $\mathcal{A}$ are localized around a single node (i. e. , an intervention propagates only to its neighbors). We then propose a novel causal bandit algorithm for an arbitrary set of interventions, which can propagate throughout the causal graph. We also show that it achieves $O(\sqrt{ \gamma^*\log(|\mathcal{A}|T) / T})$ regret bound, where $\gamma^*$ is determined by using a causal graph structure. In particular, if the maximum in-degree of the causal graph is a constant, then $\gamma^* = O(N^2)$, where $N$ is the number of nodes.

NeurIPS Conference 2018 Conference Paper

Regret Bounds for Online Portfolio Selection with a Cardinality Constraint

• Shinji Ito
• Daisuke Hatano
• Hanna Sumita
• Akihiro Yabe
• Takuro Fukunaga
• Naonori Kakimura
• Ken-ichi Kawarabayashi

Online portfolio selection is a sequential decision-making problem in which a learner repetitively selects a portfolio over a set of assets, aiming to maximize long-term return. In this paper, we study the problem with the cardinality constraint that the number of assets in a portfolio is restricted to be at most k, and consider two scenarios: (i) in the full-feedback setting, the learner can observe price relatives (rates of return to cost) for all assets, and (ii) in the bandit-feedback setting, the learner can observe price relatives only for invested assets. We propose efficient algorithms for these scenarios that achieve sublinear regrets. We also provide regret (statistical) lower bounds for both scenarios which nearly match the upper bounds when k is a constant. In addition, we give a computational lower bound which implies that no algorithm maintains both computational efficiency, as well as a small regret upper bound.

MFCS Conference 2018 Conference Paper

The b-Branching Problem in Digraphs

• Naonori Kakimura
• Naoyuki Kamiyama
• Kenjiro Takazawa

In this paper, we introduce the concept of b-branchings in digraphs, which is a generalization of branchings serving as a counterpart of b-matchings. Here b is a positive integer vector on the vertex set of a digraph, and a b-branching is defined as a common independent set of two matroids defined by b: an arc set is a b-branching if it has at most b(v) arcs sharing the terminal vertex v, and it is an independent set of a certain sparsity matroid defined by b. We demonstrate that b-branchings yield an appropriate generalization of branchings by extending several classical results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b-branching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b-branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b-branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b(v) arcs sharing the terminal vertex v.

IJCAI Conference 2017 Conference Paper

An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization

• Hanna Sumita
• Yuma Yonebayashi
• Naonori Kakimura
• Ken-ichi Kawarabayashi

This paper focuses on a generalization of the traveling salesman problem (TSP), called the subpath planning problem (SPP). Given 2n vertices and n independent edges on a metric space, we aim to find a shortest tour that contains all the edges. SPP is one of the fundamental problems in both artificial intelligence and robotics. Our main result is to design a 1. 5-approximation algorithm that runs in polynomial time, improving the currently best approximation algorithm. The idea is direct use of techniques developed for TSP. In addition, we propose a generalization of SPP called the subgroup planning problem (SGPP). In this problem, we are given a set of disjoint groups of vertices, and we aim to find a shortest tour such that all the vertices in each group are traversed sequentially. We propose a 3-approximation algorithm for SGPP. We also conduct numerical experiments. Compared with previous algorithms, our algorithms improve the solution quality by more than 10% for large instances with more than 10, 000 vertices.

TCS Journal 2017 Journal Article

Efficient stabilization of cooperative matching games

• Takehiro Ito
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

Cooperative matching games have drawn much interest partly because of the connection with bargaining solutions in the networking environment. However, it is not always guaranteed that a network under investigation gives rise to a stable bargaining outcome. To address this issue, we consider a modification process, called stabilization, that yields a network with stable outcomes, where the modification should be as small as possible. Therefore, the problem is cast to a combinatorial-optimization problem in a graph. Recently, the stabilization by edge removal was shown to be NP-hard. On the contrary, in this paper, we show that other possible ways of stabilization, namely, edge addition, vertex removal and vertex addition, are all polynomial-time solvable. Thus, we obtain a complete complexity-theoretic classification of the natural four variants of the network stabilization problem. We further study weighted variants and prove that the variants for edge addition and vertex removal are NP-hard.

NeurIPS Conference 2017 Conference Paper

Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation

• Shinji Ito
• Daisuke Hatano
• Hanna Sumita
• Akihiro Yabe
• Takuro Fukunaga
• Naonori Kakimura
• Ken-ichi Kawarabayashi

Online sparse linear regression is the task of applying linear regression analysis to examples arriving sequentially subject to a resource constraint that a limited number of features of examples can be observed. Despite its importance in many practical applications, it has been recently shown that there is no polynomial-time sublinear-regret algorithm unless NP$\subseteq$BPP, and only an exponential-time sublinear-regret algorithm has been found. In this paper, we introduce mild assumptions to solve the problem. Under these assumptions, we present polynomial-time sublinear-regret algorithms for the online sparse linear regression. In addition, thorough experiments with publicly available data demonstrate that our algorithms outperform other known algorithms.

AAMAS Conference 2016 Conference Paper

Efficient Stabilization of Cooperative Matching Games

• Takehiro Ito
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

SODA Conference 2016 Conference Paper

Exact and Approximation Algorithms for Weighted Matroid Intersection

• Chien-Chung Huang 0001
• Naonori Kakimura
• Naoyuki Kamiyama

In this paper, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a (1 – ∊)-approximate solution with a running time significantly faster than known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. Precisely speaking, we prove that we can solve the weighted matroid intersection problem via solving W instances of the unweighted matroid intersection problem, where W is the largest given weight. Furthermore, we can find a (1 – ∊)-approximate solution via solving O (∊ –1 log r ) instances of the unweighted matroid intersection problem, where r is the smallest rank of the given two matroids. Our algorithms are simple and flexible: they can be adapted to special cases of the weighted matroid intersection problem, using specialized unweighted matroid intersection algorithms. In this paper, we will show the following results. 1. Given two general matroids, using Cunningham's algorithm, we can solve the weighted matroid intersection problem exactly in O ( τWnr 1. 5 ) time and (1 – ∊)-approximately in O ( τ ∊ –1 nr 1. 5 log r ) time, where n is the size of the ground set and τ is the time complexity of an independence oracle call. 2. Given two graphic matroids, using the algorithm of Gabow and Xu, we can solve the weighted matroid intersection problem exactly in O ( τWnr 1. 5 ) time and (1 – ∊)-approximately in O ( τ∊ −1 nr 1. 5 log r time. 3. Given two linear matroids (in the form of two r -by- n matrices), using the algorithm of Cheung, Kwok, and Lau, we can solve the weighted matroid intersection problem exactly in time and (1 – ∊)-approximately in time, where ω is the exponent of the matrix multiplication time and r * is the maximum size of a common independent set. Finally, we give a further application of our decomposition technique. We use our technique to solve efficiently the rank-maximal matroid intersection problem, a problem motivated by matching problems under preferences.

TCS Journal 2015 Journal Article

Fixed-parameter tractability for subset feedback set problems with parity constraints

• Naonori Kakimura
• Ken-ichi Kawarabayashi

The subset feedback set problem, which is a generalization of the well-known feedback vertex set problem, is that we are given an undirected graph G with a vertex subset S and a positive integer k, and the goal is to find a vertex set X of size at most k such that G − X has no S-cycle, where an S-cycle is a cycle having at least one vertex of S. It was recently shown that this problem is fixed parameter tractable, where k is the parameter. In this paper, we further generalize this problem to one with the parity constraints, and show the fixed parameter tractability: 1. For a parameter k, there exists a fixed-parameter algorithm that either finds a vertex set X of size k such that G − X has no S-cycle of even length, or concludes that such a vertex set does not exist. 2. For a parameter k, there exists a fixed-parameter algorithm that either finds a vertex set X of size k such that G − X has no S-cycle of odd length, or concludes that such a vertex set does not exist.

ICML Conference 2015 Conference Paper

Threshold Influence Model for Allocating Advertising Budgets

• Atsushi Miyauchi 0001
• Yuni Iwamasa
• Takuro Fukunaga
• Naonori Kakimura

We propose a new influence model for allocating budgets to advertising channels. Our model captures customer’s sensitivity to advertisements as a threshold behavior; a customer is expected to be influenced if the influence he receives exceeds his threshold. Over the threshold model, we discuss two optimization problems. The first one is the budget-constrained influence maximization. We propose two greedy algorithms based on different strategies, and analyze the performance when the influence is submodular. We then introduce a new characteristic to measure the cost-effectiveness of a marketing campaign, that is, the proportion of the resulting influence to the cost spent. We design an almost linear-time approximation algorithm to maximize the cost-effectiveness. Furthermore, we design a better-approximation algorithm based on linear programming for a special case. We conduct thorough experiments to confirm that our algorithms outperform baseline algorithms.

ICML Conference 2014 Conference Paper

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

• Tasuku Soma
• Naonori Kakimura
• Kazuhiro Inaba
• Ken-ichi Kawarabayashi

We consider the budget allocation problem over bipartite influence model proposed by Alon et al. This problem can be viewed as the well-known influence maximization problem with budget constraints. We first show that this problem and its much more general form fall into a general setting; namely the monotone submodular function maximization over integer lattice subject to a knapsack constraint. Our framework includes Alon et al. ’s model, even with a competitor and with cost. We then give a (1-1/e)-approximation algorithm for this more general problem. Furthermore, when influence probabilities are nonincreasing, we obtain a faster (1-1/e)-approximation algorithm, which runs essentially in linear time in the number of nodes. This allows us to implement our algorithm up to almost 10M edges (indeed, our experiments tell us that we can implement our algorithm up to 1 billion edges. It would approximately take us only 500 seconds.).

SODA Conference 2012 Conference Paper

Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing

• Naonori Kakimura
• Ken-ichi Kawarabayashi
• Yusuke Kobayashi 0001