3.4k citations · 3.9k across the 67 of their papers we have counts for
Showing 2017 · cs.DSShow all
3 papers · 2 filters
cs.DS2017
A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity
Tasuku Soma, Yuichi Yoshida
In monotone submodular function maximization, approximation guarantees based on the curvature of the objective function have been extensively studied in the literature. However, th…
cs.DS2017
Cheeger Inequalities for Submodular Transformations
Yuichi Yoshida
The Cheeger inequality for undirected graphs, which relates the conductance of an undirected graph and the second smallest eigenvalue of its normalized Laplacian, is a cornerstone…
cs.DS2017
0/1/all CSPs, Half-Integral -path Packing, and Linear-Time FPT Algorithms
Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida
A recent trend in the design of FPT algorithms is exploiting the half-integrality of LP relaxations. In other words, starting with a half-integral optimal solution to an LP relaxat…