4 citations · 12 across the 21 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.DS2017
Stochastic Packing Integer Programs with Few Queries
Takanori Maehara, Yutaro Yamaguchi
We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entr…
math.CO2017
Antimatroids Induced by Matchings
Yasushi Kawase, Yutaro Yamaguchi
We explore novel connections between antimatroids and matchings in bipartite graphs. In particular, we prove that a combinatorial structure induced by stable matchings or maximum-w…
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…