Showing 2026Show all
2 papers · 1 filter
cs.CC2026
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…
math.OC2026
Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach
Nathan Benedetto Proença, Marcel K. de Carli Silva, Cristiane M. Sato +1
We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we s…