Tatsuya Terao

activity

20242026

collaborators

5 papers

cs.DS2026

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 $r \times n$ matrices $M_{1}$ and $M_{2}$ , and the objective i…

cs.DS2026

Polynomial Kernels with Reachability for Weighted $d$ -Matroid Intersection

Chien-Chung Huang, Naonori Kakimura, Yusuke Kobayashi +1

This paper studies randomized polynomial kernelization for the weighted $d$ -matroid intersection problem. While the problem is known to have a kernel of size $O (d^{(k - 1) d})$ wher…

cs.DS2025

Deterministic $(2/3 - ε)$ -Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries

Tatsuya Terao

In the matroid intersection problem, we are given two matroids $M_{1} = (V, I_{1})$ and $M_{2} = (V, I_{2})$ defined on the same ground set $V$ of $…

quant-ph2024

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 $k$ -vertex cover and $k$ -matching pro…

cs.DS2024

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 $(1 - 1/ e - I^µ)$ -approximation algorithm that requires $…

Faster Approximate Linear Matroid Intersection

Polynomial Kernels with Reachability for Weighted d-Matroid Intersection

Deterministic (2/3−ε)-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries

Parameterized Quantum Query Algorithms for Graph Problems

Subquadratic Submodular Maximization with a General Matroid Constraint

Polynomial Kernels with Reachability for Weighted $d$ -Matroid Intersection

Deterministic $(2/3 - ε)$ -Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries