4 papers
Auction-Based Algorithms for Matroid Intersection: Near-Linear Query Complexity and Constant-Pass Semi-Streaming
Chien-Chung Huang, Yusuke Kobayashi
In this paper, we develop a new auction-based framework for matroid intersection and use it to obtain improved approximation algorithms in several computational settings. Our frame…
An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
Afrouz Jabal Ameli, Yusuke Kobayashi, Takashi Noguchi
In the 2-Vertex-Connected Spanning Subgraph problem (2-VCSS), we are given an undirected graph , and the objective is to find a 2-vertex-connected spanning subgraph of w…
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…
A PTAS for Weighted Triangle-free 2-Matching
Miguel Bosch-Calvo, Fabrizio Grandoni, Yusuke Kobayashi +1
In the Weighted Triangle-Free 2-Matching problem (WTF2M), we are given an undirected edge-weighted graph. Our goal is to compute a maximum-weight subgraph that is a 2-matching (i.e…