From the 1 of 5 linked papers with an AI index.
5 papers
Optimal PSPACE-hardness of Approximating -CSP Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
The paper proves that approximating the Maxmin q‑CSP Reconfiguration problem within a factor of 1/2^{q‑1}+ε is PSPACE‑hard for any q≥2, and shows that achieving a (1/2^{q‑1}‑ε)‑app…
On (In)approximability of MaxMin Independent Set Reconfiguration
Hung P. Hoang, Naoto Ohsaka, Rin Saito +1
In the Independent Set Reconfiguration problem under the Token Addition/Removal rule, given a graph and two independent sets and of , we want to transform into $…
Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga +3
In reconfiguration problems, we are given two feasible solutions to a graph problem and asked whether one can be transformed into the other via a sequence of feasible intermediate…
Asymptotically Optimal Inapproximability of E-SAT Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
In the Maxmin E-SAT Reconfiguration problem, we are given a satisfiable -CNF formula where each clause contains exactly literals, along with a pair of its satisfying…
Matroid Semi-Bandits in Sublinear Time
Ruo-Chun Tzeng, Naoto Ohsaka, Kaito Ariu
We study the matroid semi-bandits problem, where at each round the learner plays a subset of arms from a feasible set, and the goal is to maximize the expected cumulative linea…