用自动化方法寻找k服务器猜想的潜在函数,验证其可行性。
$k$-server-bench: Automating Potential Discovery for the $k$-Server Conjecture
- 构建代码挑战自动发现满足线性不等式的潜在函数。
- 在k=3时成功解决非平凡实例,k=4时减少不满足约束数。
- 适合研究算法竞争分析与智能探索代理的学者使用。
我们提出一个基于代码的开放式数学发现挑战,针对竞争分析中的核心难题——k-服务器猜想。任务是寻找一个潜在函数,使其满足大规模图结构化的简单线性不等式系统。评估过程严谨但不完备:任一不等式被违反即可否定候选解,而所有不等式均满足仅提供强有力证据,不构成完整证明。目前,在未解决的k=4圆情形下,尚无已知潜在函数能通过该框架。因此,成功找到符合条件的候选解将是对该猜想的重要贡献,并可能发展为重大理论成果。k=3情形的实验表明,当前智能体方法可解决非平凡实例;在k=4情形中,新方法虽未完全解决任务,但相较已有潜在函数显著减少不满足约束的数量。这些结果表明该任务虽具挑战性,但现有方法有望实现突破。该任务不仅推动了对k-服务器问题的研究,还为开发基于代码的发现型智能体提供了有效基准,尤其在避免早期饱和和提升基线区分度方面优于现有开放式基准。
原文摘要 · Abstract (English)
We introduce a code-based challenge for automated, open-ended mathematical discovery based on the $k$-server conjecture, a central open problem in competitive analysis. The task is to discover a potential function satisfying a large graph-structured system of simple linear inequalities. The resulting evaluation procedure is sound but incomplete: any violated inequality definitively refutes a candidate, whereas satisfying all inequalities does not by itself constitute a proof of the corresponding conjecture's special case. Nevertheless, a candidate that passes all constraints would be strong evidence toward a valid proof and, to the best of our knowledge, no currently known potential achieves this under our formulation in the open $k=4$ circle case. As such, a successful candidate would already be an interesting contribution to the $k$-server conjecture, and could become a substantial theoretical result when paired with a full proof. Experiments on the resolved $k=3$ regime show that current agentic methods can solve nontrivial instances, and in the open $k=4$ regime they reduce the number of violations relative to existing potentials without fully resolving the task. Taken together, these results suggest that the task is challenging but plausibly within reach of current methods. Beyond its relevance to the $k$-server community, where the developed tooling enables researchers to test new hypotheses and potentially improve on the current record, the task also serves as a useful \emph{benchmark} for developing code-based discovery agents. In particular, our $k=3$ results show that it mitigates important limitations of existing open-ended code-based benchmarks, including early saturation and the weak separation between naive random baselines and more sophisticated methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。