{"681471":{"#nid":"681471","#data":{"type":"event","title":"PhD Defense by Aditya Pillai","body":[{"value":"\u003Cp\u003ETitle: Approximation and optimization approaches for graph cuts, experimental design, and routing problems\u003Cbr\u003EDate: 4\/7\/2025\u003Cbr\u003ETime: 12:30-2:30 pm\u003Cbr\u003ELocation: ISyE Studio 109\u003C\/p\u003E\u003Cp\u003EAditya Pillai\u003Cbr\u003EACO PhD Student\u003Cbr\u003EH. Milton Stewart School of Industrial and Systems Engineering\u003Cbr\u003EGeorgia Institute of Technology\u003C\/p\u003E\u003Cp\u003ECommittee:\u003Cbr\u003EDr. Mohit Singh (Advisor), School of Industrial and Systems Engineering, Georgia Institute of Technology\u003Cbr\u003EDr. Santanu Dey, School of Industrial and Systems Engineering, Georgia Institute of Technology\u003Cbr\u003EDr. Anton Kleywegt, School of Industrial and Systems Engineering, Georgia Institute of Technology\u003Cbr\u003EDr. Sahil Singla, School of Computer Science, Georgia Institute of Technology\u003Cbr\u003EDr. Weijun Xie, School of Industrial and Systems Engineering, Georgia Institute of Technology\u003Cbr\u003E\u003Cbr\u003E\u003Cbr\u003EAbstract:\u0026nbsp;\u003Cbr\u003EThis dissertation explores three topics: maximum graph cuts, design of experiments, and the traveling salesman problem.\u003Cbr\u003E\u003Cbr\u003EFirst, 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.\u003Cbr\u003E\u003Cbr\u003EThe 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.\u003C\/p\u003E\u003Cp\u003EIn 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.\u003Cbr\u003E\u003Cbr\u003EIn 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.\u003Cbr\u003E\u003Cbr\u003EFinally, 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.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":"","format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EApproximation and optimization approaches for graph cuts, experimental design, and routing problems\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Approximation and optimization approaches for graph cuts, experimental design, and routing problems"}],"uid":"27707","created_gmt":"2025-03-31 18:27:34","changed_gmt":"2025-03-31 18:27:34","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2025-04-07T12:30:21-04:00","event_time_end":"2025-04-07T14:30:21-04:00","event_time_end_last":"2025-04-07T14:30:21-04:00","gmt_time_start":"2025-04-07 16:30:21","gmt_time_end":"2025-04-07 18:30:21","gmt_time_end_last":"2025-04-07 18:30:21","rrule":null,"timezone":"America\/New_York"},"location":"ISyE Studio 109","extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}