Tatsuya Terao

most citedSubquadratic Submodular Maximization with a General Matroid Constraint

1 citations · 1 across the 2 of their papers we have counts for

collaborators

4 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.DS2024

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

cs.DS2024★ 1 cited

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 - ε)$ -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

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