1 citations · 1 across the 4 of their papers we have counts for
8 papers
A Matroid Generalization of Weighted Popular Matching: Characterization and Algorithm
Yuni Iwamasa, Yusuke Kobayashi, Ryoga Mahara +1
We study a problem that unifies two major generalizations of popular matchings in the one-sided preference model. In a bipartite graph in which each vertex, or applicant, on one si…
Dense Pinwheel Packing Is Strongly NP-Complete
Yusuke Kobayashi, Bingkai Lin, Joseph Swernofsky
An instance of {\sc Pinwheel Packing} is a list of positive integers . A feasible schedule assigns one task to every integer time so that every interval of co…
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…
On the two problems in Ramsey achievement games
Zhong Huang, Yusuke Kobayashi, Yaping Mao +2
Let be two integers with . Given a finite graph with no isolated vertices, the generalized Ramsey achievement game of on the complete graph , denoted by…
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 $\…
Finding a Maximum Restricted -Matching via Boolean Edge-CSP
Yuni Iwamasa, Yusuke Kobayashi, Kenjiro Takazawa
The problem of finding a maximum -matching without short cycles has received significant attention due to its relevance to the Hamilton cycle problem. This problem is generalize…
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…