Yusuke Kobayashi

activity

20202026

most citedSubquadratic Submodular Maximization with a General Matroid Constraint

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

collaborators

Showing 2024Show all

3 papers · 1 filter

cs.DS2024

Validating a PTAS for Triangle-Free 2-Matching via a Simple Decomposition Theorem

Yusuke Kobayashi, Takashi Noguchi

A triangle-free (simple) 2-matching is an edge set that has at most $2$ edges incident to each vertex and contains no cycle of length $3$ . For the problem of finding a maximum card…

math.CO2024

On the two problems in Ramsey achievement games

Zhong Huang, Yusuke Kobayashi, Yaping Mao +2

Let $p, q$ be two integers with $p \geq q$ . Given a finite graph $F$ with no isolated vertices, the generalized Ramsey achievement game of $F$ on the complete graph $K_{n}$ , denoted by…

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