5th Year Master's Thesis Presentation - Tianwei Owen Li

— 2:00pm

Location:
In Person - Blelloch-Skees Conference Room, Gates Hillman 8115

Speaker:
TIANWEI OWEN LI , Master's Student, Computer Science Department, Carnegie Mellon University

Two Simple Algorithmic Applications of Convex Optimization

Methods and concepts from convex optimization have close relations to traditionally discrete algorithms, and we investigate two separate cases of such. In part I, we leverage a variant of the Mirror-Prox algorithm from Sherman’s 2017 paper on area-convexity and multicommodity flow, to design a fast Õ(m/ε) algorithm for ε-fair cuts, a special type of approximate st-min-cut that requires some st-flow to 1 − ε saturate all edges across the cut. Such runtime is an improvement over the state-of-the-art Õ(m/ε3), and the resulting algorithm is much simpler.  In part II, we design a continuous variant of the Graham Scan convex hull algorithm that computes the tight convex envelope of degree-n univariate polynomials in O(n3 + n log2 n log b + nb2) with respect to an interval domain, and updates in O(b2) with respect to a new interval domain, where 2−b  is the relative precision for float point arithmetic. Such an algorithm relies on properties of convex functions for its proof of correctness, and can be used to construct high quality convex relaxations for Generalized Additive Models (GAM) with monotone link functions. 

Thesis Committee

Barnabás Póczos (Chair)
Jason Li

Additional Information

Add event to Google
Add event to iCal