Tatsuya Terao

collaborators

3 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 $…

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

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

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