5 citations · 11 across the 22 of their papers we have counts for
32 papers
Vertex Cover Interdiction in Bipartite Graphs
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
In the vertex cover interdiction problem, we are given an undirected graph , two integers and and a vertex subset , and we are asked to find a set $X…
A Refined Analysis of the Sequential Access Theorem for Splay Trees
Naonori Kakimura, Yoshihiko Terai
A splay tree is a self-adjusting binary search tree that allows access, insertion, and deletion to be performed in amortized time, where is the number of stored ele…
A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
Philip Cervenjak, Junhao Gan, Naonori Kakimura +2
Connected Submodular Maximization (CSM) is a graph problem with important applications to wireless network deployment, path planning, epidemic outbreaks, and cancer genome studies.…
Polynomial Kernels with Reachability for Weighted -Matroid Intersection
Chien-Chung Huang, Naonori Kakimura, Yusuke Kobayashi +1
This paper studies randomized polynomial kernelization for the weighted -matroid intersection problem. While the problem is known to have a kernel of size wher…
Computing Power Indices in Weighted Majority Games with Formal Power Series
Naonori Kakimura, Yoshihiko Terai
In this paper, we propose fast pseudo-polynomial-time algorithms for computing power indices in weighted majority games. We show that we can compute the Banzhaf index for all playe…
Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
The minimum sum coloring problem with bundles was introduced by Darbouy and Friggstad (SWAT 2024) as a common generalization of the minimum coloring problem and the minimum sum col…
Simultaneous Network Design with Restricted Link Usage
Naonori Kakimura, Péter Madarasi, Jannik Matuschke +1
Given a digraph with two terminal vertices and as well as a conservative cost function and several not necessarily disjoint color classes on its arc set, our goal is to fin…
Loss Minimization for Electrical Flows over Spanning Trees on Grids
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
We study the electrical distribution network reconfiguration problem, defined as follows. We are given an undirected graph with a root vertex, demand at each non-root vertex, and r…
Reconfiguration of labeled matchings in triangular grid graphs
Naonori Kakimura, Yuta Mishima
This paper introduces a new reconfiguration problem of matchings in a triangular grid graph. In this problem, we are given a nearly perfect matching in which each matching edge is…
On Approximating the Weighted Region Problem in Square Tessellations
Naonori Kakimura, Rio Katsu
The weighted region problem is the problem of finding the weighted shortest path on a plane consisting of polygonal regions with different weights. For the case when the plane is t…
Parameterized Complexity of Submodular Minimization under Uncertainty
Naonori Kakimura, Ildikó Schlotter
This paper studies the computational complexity of a robust variant of a two-stage submodular minimization problem that we call Robust Submodular Minimizer. In this problem, we are…
New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem
Koji Ichikawa, Shinji Ito, Daisuke Hatano +4
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 al…
Deterministic Primal-Dual Algorithms for Online k-way Matching with Delays
Naonori Kakimura, Tomohiro Nakayoshi
In this paper, we study the Min-cost Perfect -way Matching with Delays (-MPMD), recently introduced by Melnyk et al. In the problem, requests arrive one-by-one over time…
Algorithmic Theory of Qubit Routing
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum progra…
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +4
We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open pro…
Rerouting Planar Curves and Disjoint Paths
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura +5
In this paper, we consider a transformation of disjoint paths in a graph. For a graph and a pair of disjoint paths and connecting the same set o…
On Reachable Assignments under Dichotomous Preferences
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +4
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.…
Reforming an Envy-Free Matching
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura +5
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…
Online Task Assignment Problems with Reusable Resources
Hanna Sumita, Shinji Ito, Kei Takemura +4
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…
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura +6
We initiate the study of -edge-connected orientations of undirected graphs through edge flips for . We prove that in every orientation of an undirected -edge-conne…
Dynamic Bipartite Matching Market with Arrivals and Departures
Naonori Kakimura, Donghao Zhu
In this paper, we study a matching market model on a bipartite network where agents on each side arrive and depart stochastically by a Poisson process. For such a dynamic model, we…
Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions
Kei Takemura, Shinji Ito, Daisuke Hatano +4
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…
Market Pricing for Matroid Rank Valuations
Kristóf Bérczi, Naonori Kakimura, Yusuke Kobayashi
In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable to achieve o…
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
Chien-Chung Huang, Naonori Kakimura, Simon Mauras +1
Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements…