[Online Seminar] Frugal Algorithm Selection for Combinatorial Search by Erdem Kus

Dear all,

Neural Computation Unit (Doya Unit) would like to invite you to a online seminar as follows.

Speaker: Erdem Kus  (University of St Andrews)

Title: Frugal Algorithm Selection for Combinatorial Search

Abstract: 

Solvers for combinatorial search and optimisation problems often show highly complementary performance: instances that are difficult for one solver may be easy for another. The Algorithm Selection Problem addresses this challenge by predicting which solver will perform best for each problem instance. However, training machine learning models for algorithm selection is often expensive because it typically requires running every solver on every training instance to obtain ground-truth performance data.

In this work, we propose a frugal approach that formulates algorithm selection as an active learning problem. Rather than exhaustively evaluating all solver–instance pairs, the proposed method selectively acquires the most informative performance observations, substantially reducing the cost of data collection. We show that standard active learning methods are insufficient in this setting because they do not account for the distinctive structure and evaluation costs of algorithm selection. To address this limitation, we introduce cost-aware active learning strategies that use surrogate models for runtime and timeout prediction to balance informativeness with evaluation cost. Experiments across a diverse collection of combinatorial search scenarios demonstrate that the proposed approach can achieve competitive algorithm-selection performance while reducing the required labelling cost by up to 90%.

Zoom URL:https://oist.zoom.us/j/92712490586?pwd=g4Vn0gCPzL4Z9NUiDRMwGL5nX7txWa.1

ID:927 1249 0586
Passcode:702129

We hope to see many of you at the seminar.

Sincerely,
Neural Computation Unit
Contact: ncus@oist.jp