ACO Defense of Research Proposal of Aditya Pillai, August 25, 2023
Title: Approximation Algorithms for Cut and Connectivity Problems
ACO PhD student, School of Industrial and Systems Engineering
Date: August 25
Location: Groseclose 118
Time: 2:00 pm
Committee:
Dr. Mohit Singh (Advisor), Professor, School of Industrial & Systems Engineering, Georgia Institute of Technology
Dr. Weijun Xie, Assistant Professor, School of Industrial & Systems Engineering, Georgia Institute of Technology
Dr. Santanu Dey, Professor and Associate Chair for Graduate Studies, School of Industrial & Systems Engineering, Georgia Institute of Technology
Dr. Sahil Singla, Assistant Professor, School of Computer Science, Georgia Institute of Technology
Abstract:
Cuts and connectivity are fundamental properties of graphs that are studied extensively due to their importance in many discrete optimization problems. In this proposal, we outline ongoing and future work directions on cut and connectivity problems.
Finding a cut in a graph of maximum value is a well-known problem that has spawned research in multiple areas including approximation algorithms. In our first work, we give an improved approximation algorithm for Max-$3$-section where the goal is to partition the vertex set of a graph into 3 equal-sized parts such the number of edges between parts is maximized. This work is joint with Dor Katzelnick, Roy Schwartz, and Mohit Singh and will appear in European Symposium on Algorithms (ESA) 2023.
The Traveling Salesman Problem (TSP) is one of the most well-known problems in combinatorial optimization and crucially uses properties of connectivity in graphs. A variant of TSP is multi-visit TSP where 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 the second work (in submission), with Mohit Singh, we show that a Linear Programming relaxation based algorithm for TSP can be converted to one for multi-visit TSP with the same approximation factor. We also apply our reduction to several variants of multi-visit TSP to either improve the current best approximation factors or to recover the current best bounds.
The third part of the proposal is (ongoing) work with Mohit Singh and Weijun Xie on D-optimal design, a problem that lies in the intersection of statistics and optimization. The goal is to estimate a vector $\beta$ in $d$-dimensions using $n$ linear measurements in the presence of Gaussian noise. We find and utilize connections of D-optimal design to the max-cut problem and its generalizations. Unlike the previous two works which are primarily theoretical, here we also discuss many ideas for implementation of algorithms for D-optimal design.
