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
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