The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics
This work addresses long-standing open problems in theoretical computer science by demonstrating a human-AI collaboration approach to break barriers in combinatorial optimization, though it is incremental in refining existing methods.
The paper tackled the problem of generating adversarial instances for combinatorial optimization heuristics by combining human expertise with LLM-based evolutionary methods, resulting in state-of-the-art lower bounds for problems like hierarchical k-median clustering and bin packing, some of which had not seen improvement for over a decade.
We demonstrate the power of human-LLM collaboration in tackling open problems in theoretical computer science. Focusing on combinatorial optimization, we refine outputs from the FunSearch algorithm [Romera-Paredes et al., Nature 2023] to derive state-of-the-art lower bounds for standard heuristics. Specifically, we target the generation of adversarial instances where these heuristics perform poorly. By iterating on FunSearch's outputs, we identify improved constructions for hierarchical $k$-median clustering, bin packing, the knapsack problem, and a generalization of Lovász's gasoline problem - some of these have not seen much improvement for over a decade, despite intermittent attention. These results illustrate how expert oversight can effectively extrapolate algorithmic insights from LLM-based evolutionary methods to break long-standing barriers. Our findings demonstrate that while LLMs provide critical initial patterns, human expertise is essential for transforming these patterns into mathematically rigorous and insightful constructions. This work highlights that LLMs are a strong collaborative tool in mathematics and computer science research.