6 citations · 21 across the 12 of their papers we have counts for
13 papers
NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam
Taisei Otsuji, Peter Fulla, Takuro Fukunaga
Hotaru Beam is a logic puzzle which objective is to connect circles placed on a grid by drawing only lines with specified starting points and numbers of bends. A zero-knowledge pro…
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…
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…
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…
Adaptive Algorithm for Finding Connected Dominating Sets in Uncertain Graphs
Takuro Fukunaga
The problem of finding a minimum-weight connected dominating set (CDS) of a given undirected graph has been studied actively, motivated by operations of wireless ad hoc networks. I…
Causal Bandits with Propagating Inference
Akihiro Yabe, Daisuke Hatano, Hanna Sumita +4
Bandit is a framework for designing sequential experiments. In each experiment, a learner selects an arm and obtains an observation corresponding to . Theore…
Submodular maximization with uncertain knapsack capacity
Yasushi Kawase, Hanna Sumita, Takuro Fukunaga
We consider the maximization problem of monotone submodular functions under an uncertain knapsack constraint. Specifically, the problem is discussed in the situation that the knaps…
Computing a tree having a small vertex cover
Takuro Fukunaga, Takanori Maehara
We consider a new Steiner tree problem, called vertex-cover-weighted Steiner tree problem. This problem defines the weight of a Steiner tree as the minimum weight of vertex covers…
Constant-approximation algorithms for highly connected multi-dominating sets in unit disk graphs
Takuro Fukunaga
Given an undirected graph on a node set and positive integers and , a -connected -dominating set (-CDS) is defined as a subset of such that each nod…
Approximating the generalized terminal backup problem via half-integral multiflow relaxation
Takuro Fukunaga
We consider a network design problem called the generalized terminal backup problem. Whereas earlier work investigated the edge-connectivity constraints only, we consider both edge…
Covering problems in edge- and node-weighted graphs
Takuro Fukunaga
This paper discusses the graph covering problem in which a set of edges in an edge- and node-weighted graph is chosen to satisfy some covering constraints while minimizing the sum…
Spider covers for prize-collecting network activation problem
Takuro Fukunaga
In the network activation problem, each edge in a graph is associated with an activation function, that decides whether the edge is activated from node-weights assigned to its end-…
Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
Takuro Fukunaga, Zeev Nutov, R. Ravi
We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iter…