Back to search

University of Waterloo

A Primal-Dual Framework for Approximation Algorithms using Semidefinite Programming

Abstract

dc:description.abstract

Duality 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 × 8

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/24079

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Benedetto Proença, Nathan. A Primal-Dual Framework for Approximation Algorithms using Semidefinite Programming. University of Waterloo, 2026. https://hdl.handle.net/10012/24079