University of Waterloo
A Primal-Dual Framework for Approximation Algorithms using Semidefinite Programming
Abstract
dc:description.abstractDuality lies in the foundation of mathematical optimization. Within combinatorial optimization, linear programming (LP) duality crucially allows for polynomial-sized proofs of optimality, guiding the design of several algorithms. This work exploits a set of alternative formulations of convex duality to design primal-dual approximation algorithms for NP-hard problems. The focus lies on the literature that followed the celebrated Goemans and Williamson approximation algorithm for the maximum cut problem, and thus on the use of semidefinite programming (SDP). We present a primal-dual conic optimization framework that pairs, via gauge and antiblocking duality, an NP-hard problem with a new NP-hard problem stated as a convex optimization problem with exponentially many variables. For the maximum cut problem, the corresponding dual is the weighted fractional cut-covering problem. Notable applications of the framework include finding an optimal assignment for any Boolean constraint satisfaction problem (CSP) on two variables, as well as maximizing a convex quadratic form over the hypercube. For each NP-hard pair, our algorithms solve a single SDP relaxation and generate feasible solutions for both problems, which also provide approximate optimality certificates for each other. Many randomized algorithms with the best known approximation factors for the primal problem are refined into a primal-dual algorithm with the same approximation quality. These results thus refine certain uses of Ellipsoid and Multiplicative-Weights Update methods. We prove our algorithms and analyses to be optimal in several aspects. Extensive experimental work is provided on the special case of maximum cut and fractional cut-covering problems. We present several implementations which reliably achieve the Goemans and Williamson approximation ratio for both optimization problems simultaneously, after sampling ⌈128 ln m⌉ cuts, significantly fewer than the best theoretical bounds. This is the first experimental work approximating the weighted fractional cut-covering problem. Careful pre-processing of instances and post-processing of numeric results allow for good empirical outcomes with both first- and second-order SDP solvers. This work is permeated by techniques from the areas of randomized approximation algorithms, convex optimization, spectral sparsification, and measure concentration. A Banach-space version of our framework provides a novel approach for the design of rounding algorithms, and tightens the relationship between approximation algorithms for CSPs and the work of Grothendieck on tensor products of Banach spaces.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Benedetto Proença, Nathan
Subjects
dc:subject × 8Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10012/24079