Title: Approximation and optimization approaches for graph cuts, experimental design, and routing problems
Date: 4/7/2025
Time: 12:30-2:30 pm
Location: ISyE Studio 109

Aditya Pillai
ACO PhD Student
H. Milton Stewart School of Industrial and Systems Engineering
Georgia Institute of Technology

Committee:
Dr. Mohit Singh (Advisor), School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Santanu Dey, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Anton Kleywegt, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Sahil Singla, School of Computer Science, Georgia Institute of Technology
Dr. Weijun Xie, School of Industrial and Systems Engineering, Georgia Institute of Technology


Abstract: 
This dissertation explores three topics: maximum graph cuts, 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 for algorithms that require explicit enumeration of the experiment space when it is too large to feasibly list. 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 Fedorov exchange algorithm reduces to solving a quadratic optimization problem that generalizes Max-Cut. Our work includes an experimental study and a theoretical analysis that applies approximation algorithms for Max-Cut.

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 Fedorov exchange algorithm reduces to solving a Rayleigh quotient problem. We provide numerical results demonstrating scalability and show an application to gradient estimation when derivatives are unavailable.

Finally, the third part is about a variant of the traveling salesman problem (TSP) called multi-visit TSP. In multi-visit TSP, each city v 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 an LP relaxation based algorithm for TSP can be converted to an LP relaxation based algorithm for multi-visit TSP with the same approximation factor. We also apply our reduction to several variants of multi-visit TSP to improve or recover the current best approximation factors.