16 citations · 17 across the 3 of their papers we have counts for
5 papers
Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions
Kaito Fujii
This paper proposes a new framework for providing approximation guarantees of local search algorithms. Local search is a basic algorithm design technique and is widely used for var…
An improved algorithm for the submodular secretary problem with a cardinality constraint
Kaito Fujii
We study the submodular secretary problem with a cardinality constraint. In this problem, candidates for secretaries appear sequentially in random order. At the arrival of each…
Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
Kaito Fujii, Shinsaku Sakaue
We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide v…
Fast greedy algorithms for dictionary selection with generalized sparsity constraints
Kaito Fujii, Tasuku Soma
In dictionary selection, several atoms are selected from finite candidates that successfully approximate given data points in the sparse representation. We propose a novel efficien…
Polynomial-Time Algorithms for Submodular Laplacian Systems
Kaito Fujii, Tasuku Soma, Yuichi Yoshida
Let be an undirected graph, be the associated Laplacian matrix, and be a vector. Solving the Laplacian system $L_G x…