4 papers
Robust Approximation and the Arity Barrier at Width Two
Nathan Benedetto Proença, Koppány István Encz, Monaldo Mastrolilli
Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite constraint langu…
Integrality gap preserving reductions
Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi
We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, calle…
QEDBENCH: Quantifying the Alignment Gap in Automated Evaluation of University-Level Mathematical Proofs
Santiago Gonzalez, Alireza Amiri Bavandpour, Peter Ye +48
As Large Language Models (LLMs) saturate elementary benchmarks, the research frontier has shifted from generation to the reliability of automated evaluation. We demonstrate that st…
Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi
Branch-and-bound algorithms (B&B) and polynomial-time approximation schemes (PTAS) are two seemingly distant areas of combinatorial optimization. We intend to (partially) bridge th…