Software Engineer Intern at Google
Jan - Mar 2019
• Scheduling problems with applications in High Performance Computing (HPC)
⁃ STACS’18 improved bounds on scheduling under precedence and power constraints by an exponential factor using novel linear programming relaxations
⁃ SuperComputing’18 extended these bounds to configurable HPC setting and demonstrated better performance than state-of-the-art schedulers: [github.com/PowerCapDAG]
• Clustering problems such as k-means, k-median, and facility location
⁃ ICALP’16 improved capacity violation factor of k-median problem significantly by solving an exponentially large LP relaxation using a tricky separation oracle for the ellipsoid method
Jan - Mar 2019
Jun - Sep 2016
Designed and implemented a more efficient algorithm for a key component of a new trading strategy. Did hyperparameter search for the new strategy and backtested it.
Thesis: Constant Approximation for Capacitated k-Median with (1 + \epsilon)-Capacity Violation
Thesis: The Complexity of Debate Checking, Advisor: Cem Say
We design an algorithm for scheduling precedence DAGs under a power-cap with an unusual paradigm: divide-and-conquer. We prove an O(log n)-approximate guarantee on its performance. We implement our algorithm and a simulation environment around power/performance data collected from real HPC applications. Comparison against several state-of-the-art "greedy" schedulers show that our algorithm performs much better especially under severe power restrictions.
We design the first algorithms with nontrivial approximation ratios for simultaneously precedence and resource constrained scheduling. Our algorithms use a divide-and-conquer approach for the minimum makespan objective. Then we make extensive use of new linear programming relaxations for generalization to weighted completion time objective and machines running at different speeds.
Capacitated k-median is a variation of the classical clustering problem with capacities specified for cluster sizes. Our work brings down the capacity violation factor from 3 to (1 + \epsilon) for a constant approximation-factor. We use an exponential size linear programming relaxation for the problem. Instead of solving the LP directly, we combine our rounding algorithm with the ellipsoid method in a "round-or-separate" fashion to solve the large LP efficiently.