1 citations · 1 across the 4 of their papers we have counts for
4 papers · 1 filter
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 edges incident to each vertex and contains no cycle of length . For the problem of finding a maximum card…
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 $\…
Frameworks to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi +4
Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world probl…
Parameterized Complexity of -Path Packing
Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki +6
Given a graph , , and integers and , the \textsc{-Path Packing} problem asks to find vertex-disjoint paths of length that h…