{"id":"arxiv/2604.17661","url":"https://arxiv.org/abs/2604.17661","tags":["math.OC","cs.DM"],"score":0,"title":"Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach","domain":"math.OC","source":"arxiv","authors":["Nathan Benedetto Proença","Marcel K. de Carli Silva","Cristiane M. Sato","Levent Tunçel"],"reviews":0,"subject":"math.OC","summary":"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 solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then simultaneously certify the approximate optimality of a cut and a fractional cut cover. We present several implementations which reliably achieve the celebrated Goemans and Williamson…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-19","reactions":{}}