Back to search

Georgia Institute of Technology

Approximation and Optimization Approaches for Graph Cuts, Experimental Design, and Routing Problems

Abstract

dc:description.abstract

This dissertation explores three topics: maximum graph cuts, the design of experiments, and the traveling salesman problem. First, we study MAX-3-SECTION, where the goal is to partition a weighted graph into three equally sized parts to maximize the weight of crossing edges. We present a new approximation algorithm that improves upon the best-known factor by rounding a semidefinite programming relaxation. The second topic focuses on design of experiments, where the objective is to select a limited subset of experiments from a universe to maximize the information gained about an underlying system. This is typically achieved by optimizing criteria such as D-optimality or A-optimality. A major challenge arises when the universe of experiments is too large to be explicitly enumerated. We address this challenge in two different settings. In the first work, we consider the case where the experiment space consists of the boolean hypercube, with D-optimality as the objective. We show that the well-known Federov exchange algorithm reduces to solving a quadratic optimization problem that generalizes MAX-CUT. We include a theoretical analysis that applies approximation algorithms for MAX-CUT similar to those used in the first part of the thesis. In the second work, we consider the case where the experiment space is the surface of the unit sphere, with A-optimality as the objective. We show that the Federov exchange algorithm reduces to solving a Rayleigh quotient problem. Both works include an experimental study demonstrating the scalability of our approach. Finally, the third part is about a variant of the traveling salesman problem (TSP) called multi-visit TSP. In multi-visit TSP, each city has a visit request r(v) and the goal is for a salesman to go on a tour so that each city is visited r(v) times. In this work, we show that a LP relaxation based algorithm for TSP can be converted to a LP relaxation based algorithm for multi-visit TSP with the same approximation factor. We apply our reduction to several variants of multi-visit TSP to either improve the current best approximation factors.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pillai, Aditya
Advisor dc:contributor.advisor
  • Singh, Mohit

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/77836

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pillai, Aditya. Approximation and Optimization Approaches for Graph Cuts, Experimental Design, and Routing Problems. Doctoral thesis, Georgia Institute of Technology, 2025. https://hdl.handle.net/1853/77836