This is the first experimental work approximating the weighted fractional cut-covering problem, and we deliver robust and repeatable results despite the use of randomized algorithms and floating-point arithmetic. Careful pre-processing of instances and post-processing of numeric results allow for good empirical outcomes with both first-order and second-order SDP solvers. Nearly optimal SDP solutions are suitably perturbed to ensure better probabilistic and numerical behavior. Our experiments deviate from theory by using a linear programming (LP) solver to compute fractional cut covers. For most instances studied, LP solving produces certifiably better results than the theoretical algorithm after \(\lceil 128 \ln m \rceil\) samples. All our experiments strictly follow a unified pipeline which explicitly documents all parameters used in each run.
Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach
\(\)
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 Goemans and Williamson approximation ratio of \(\alpha_{\mathrm{GW}} \approx 0.878\) for both optimization problems simultaneously, after \(\lceil 128 \ln m \rceil\) samples, a number significantly smaller than the best theoretical bounds.
This is the first experimental work approximating the weighted fractional cut-covering problem, and we deliver robust and repeatable results despite the use of randomized algorithms and floating-point arithmetic. Careful pre-processing of instances and post-processing of numeric results allow for good empirical outcomes with both first-order and second-order SDP solvers. Nearly optimal SDP solutions are suitably perturbed to ensure better probabilistic and numerical behavior. Our experiments deviate from theory by using a linear programming (LP) solver to compute fractional cut covers. For most instances studied, LP solving produces certifiably better results than the theoretical algorithm after \(\lceil 128 \ln m \rceil\) samples. All our experiments strictly follow a unified pipeline which explicitly documents all parameters used in each run.
This is the first experimental work approximating the weighted fractional cut-covering problem, and we deliver robust and repeatable results despite the use of randomized algorithms and floating-point arithmetic. Careful pre-processing of instances and post-processing of numeric results allow for good empirical outcomes with both first-order and second-order SDP solvers. Nearly optimal SDP solutions are suitably perturbed to ensure better probabilistic and numerical behavior. Our experiments deviate from theory by using a linear programming (LP) solver to compute fractional cut covers. For most instances studied, LP solving produces certifiably better results than the theoretical algorithm after \(\lceil 128 \ln m \rceil\) samples. All our experiments strictly follow a unified pipeline which explicitly documents all parameters used in each run.