1 citations · 1 across the 2 of their papers we have counts for
7 papers · 1 filter
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 $…
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 …