1 citations · 1 across the 2 of their papers we have counts for
8 papers
Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach
Tatsuya Terao
We present a simple deterministic semi-streaming algorithm that computes a -approximate maximum matching in general graphs in passes. This m…
A Faster Auction Algorithm for Weighted Matroid Intersection
Tatsuya Terao
We consider the weighted matroid intersection problem in the independence-oracle model. A sequence of works by Huang--Kakimura--Kamiyama [SODA'16 \& Math. Program'19], Chekuri--Qua…
Faster Approximate Linear Matroid Intersection
Tatsuya Terao
We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two matrices and , and the objective i…
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…
Deterministic -Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
Tatsuya Terao
In the matroid intersection problem, we are given two matroids and defined on the same ground set of $…
Parameterized Quantum Query Algorithms for Graph Problems
Tatsuya Terao, Ryuhei Mori
In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for -vertex cover and -matching pro…
Subquadratic Submodular Maximization with a General Matroid Constraint
Yusuke Kobayashi, Tatsuya Terao
We consider fast algorithms for monotone submodular maximization with a general matroid constraint. We present a randomized -approximation algorithm that requires $\…
Faster Matroid Partition Algorithms
Tatsuya Terao
In the matroid partitioning problem, we are given matroids defined over a common ground set …