Author name cluster

Yoichi Iwata

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

NeurIPS Conference 2025 Conference Paper

ALE-Bench: A Benchmark for Long-Horizon Objective-Driven Algorithm Engineering

Yuki Imajuku
Kohki Horie
Yoichi Iwata
Kensho Aoki
Naohiro Takahashi
Takuya Akiba

How well do AI systems perform in algorithm engineering for hard optimization problems in domains such as package-delivery routing, crew scheduling, factory production planning, and power-grid balancing? We introduce $\textit{ALE-Bench}$, a new benchmark for evaluating AI systems on score-based algorithmic programming contests. Drawing on real tasks from the AtCoder Heuristic Contests, ALE-Bench presents optimization problems that are computationally hard and admit no known exact solution. Unlike short-duration, pass/fail coding benchmarks, ALE-Bench encourages iterative solution refinement over long time horizons. Our software framework supports interactive agent architectures that leverage test-run feedback and visualizations. Our evaluation of frontier LLMs revealed that while they demonstrate high performance on specific problems, a notable gap remains compared to humans in terms of consistency across problems and long-horizon problem-solving capabilities. This highlights the need for this benchmark to foster future AI advancements.

PDF Details

AAAI Conference 2019 Conference Paper

Separator-Based Pruned Dynamic Programming for Steiner Tree

Yoichi Iwata
Takuto Shigemura

Steiner tree is a classical NP-hard problem that has been extensively studied both theoretically and empirically. In theory, the fastest approach for inputs with a small number of terminals uses the dynamic programming, but in practice, stateof-the-art solvers are based on the branch-and-cut method. In this paper, we present a novel separator-based pruning technique for speeding up a theoretically fast DP algorithm. Our empirical evaluation shows that our pruned DP algorithm is quite effective against real-world instances admitting small separators, scales to more than a hundred terminals, and is competitive with a branch-and-cut solver.

PDF Details

FOCS Conference 2018 Conference Paper

0/1/All CSPs, Half-Integral A-Path Packing, and Linear-Time FPT Algorithms

Yoichi Iwata
Yutaro Yamaguchi 0001
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 relaxation, we assign integral values to variables one-by-one by branch and bound. This technique is general and the resulting time complexity has a low dependency on the parameter. However, the time complexity often becomes a large polynomial in the input size because we need to compute half-integral optimal LP solutions. In this paper, we address this issue by providing an O(km)-time algorithm for solving the LPs arising from various FPT problems, where k is the optimal value and m is the number of edges/constraints. Our algorithm is based on interesting connections among 0/1/all constraints, which has been studied in the field of constraints satisfaction, A-path packing, which has been studied in the field of combinatorial optimization, and the LPs used in FPT algorithms. With the aid of this algorithm, we obtain linear-time FPT algorithms for various problems. The obtained running time for each problem is linear in the input size and has the current smallest dependency on the parameter. Most importantly, instead of using problem-specific approaches, we obtain all of these results by a unified approach, i. e. , the branch-and-bound framework combined with the efficient computation of half-integral LPs, which demonstrates its generality.

Details

TCS Journal 2016 Journal Article

Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover

Takuya Akiba
Yoichi Iwata

We investigate the gap between theory and practice for exact branching algorithms. In theory, branch-and-reduce algorithms currently have the best time complexity for numerous important problems. On the other hand, in practice, state-of-the-art methods are based on different approaches, and the empirical efficiency of such theoretical algorithms has seldom been investigated probably because they are seemingly inefficient because of the plethora of complex reduction rules. In this paper, we design a branch-and-reduce algorithm for the vertex cover problem using the techniques developed for theoretical algorithms and compare its practical performance with other state-of-the-art empirical methods. The results indicate that branch-and-reduce algorithms are actually quite practical and competitive with other state-of-the-art approaches for several kinds of instances, thus showing the practical impact of theoretical research on branching algorithms.

Details DOI

AAAI Conference 2015 Conference Paper

Efficient Top-k Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling

Takuya Akiba
Takanori Hayashi
Nozomi Nori
Yoichi Iwata
Yuichi Yoshida

We propose an indexing scheme for top-k shortestpath distance queries on graphs, which is useful in a wide range of important applications such as networkaware searches and link prediction. While many efficient methods for answering standard (top-1) distance queries have been developed, none of these methods are directly extensible to top-k distance queries. We develop a new framework for top-k distance queries based on 2-hop cover and then present an efficient indexing algorithm based on the recently proposed pruned landmark labeling scheme. The scalability, efficiency and robustness of our method is demonstrated in extensive experimental results. Moreover, we demonstrate the usefulness of top-k distance queries by applying them to link prediction, the most fundamental graph problem in the AI and Web communities.

PDF Details

SODA Conference 2014 Conference Paper

Linear-Time FPT Algorithms via Network Flow

Yoichi Iwata
Keigo Oka
Yuichi Yoshida

In the area of parameterized complexity, to cope with NP-Hard problems, we introduce a parameter k besides the input size n, and we aim to design algorithms (called FPT algorithms) that run in O ( f ( k ) n d ) time for some function f ( k ) and constant d. Though FPT algorithms have been successfully designed for many problems, typically they are not sufficiently fast because of huge f ( k ) and d. In this paper, we give FPT algorithms with small f ( k ) and d for many important problems including Odd Cycle Transversal and Almost 2-SAT. More specifically, we can choose f ( k ) as a single exponential (4 k ) and d as one, that is, linear in the input size. To the best of our knowledge, our algorithms achieve linear time complexity for the first time for these problems. To obtain our algorithms for these problems, we consider a large class of integer programs, called BIP2. Then we show that, in linear time, we can reduce BIP2 to Vertex Cover Above LP preserving the parameter k, and we can compute an optimal LP solution for Vertex Cover Above LP using network flow. Then, we perform an exaustive search by fixing half-integral values in the optimal LP solution for Vertex Cover Above LP. A bottleneck here is that we need to recompute an LP optimal solution after branching. To address this issue, we exploit network flow to update the optimal LP solution in linear time.

Details