*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Randomized Kernel Rounding Methods for Routing, Scheduling, and Machine Learning
Date: Wednesday, April 20, 2022
Time: 09:30am EST
Location: https://bluejeans.com/601031659 (online)
Majid Farhadi
Ph.D. Candidate
Algorithms, Combinatorics, and Optimization School of Computer Science Georgia Institute of Technology
Committee:
Dr. Swati Gupta, School of Industrial and Systems Engineering, Georgia Institute of Technology Dr. Renato D. C. Monteiro, School of Industrial and Systems Engineering, Georgia Institute of Technology Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology Dr. Santosh Vempala, College of Computing, Georgia Institute of Technology
Advisor: Dr. Prasad Tetali, Department of Mathematical Sciences, Carnegie Mellon University
Reader: Dr. Swati Gupta, School of Industrial and Systems Engineering, Georgia Institute of Technology
Thesis will be available at:
https://drive.google.com/file/d/11e6s2-KEYVaNtrLa1hL4GUyEsm20XQQ5/view?usp=sharing
Summary:
From Computer Science, Machine Learning, Communications, and Control Systems to Supply Chain, Finance, and Policy Making we make a sequence of choices, optimality of which can be decisive to maximize revenue or critical to ensure robustness, security, and reliability. In numerous cases, solving the exact problem is not feasible, e.g., due to limited computational and storage resources, missing key data, or intrinsic hardness barriers. Therefore, researchers develop algorithms to guarantee solutions that are approximately correct/optimal.
We study classical problems from combinatorial optimization and machine learning and develop near optimal approximation algorithms and computational complexity results. We introduce new randomized techniques, notably the kernel alpha-point rounding, for efficiently converting solutions of tractable convex/linear relaxations of these problems. The problems under study have immediate applications in machine learning, Ads/search systems, routing, scheduling, non-convex optimization, mathematical programming, Markov chains, and non-linear dimension reduction; to name but a few. We employ techniques from convex optimization, machine learning, linear algebra, graph theory, high dimensional geometry, combinatorics, and probability theory; and further contribute to such theories, e.g., by providing a new inequality on the lower tail of a sum of Bernoulli random variables.
