Methods and concepts from convex otpimization has close relations to traditionally discrete algorithms, and we investigate two separte cases of such. In part I, we leverage a variant of the Mirror-Prox algorithms from Sherman's 2017 paper on area-convexity and multicommodity flow, to design a fast Õ(m/ε) agorithms 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/ε³) and the resulting algorithm is much simpler. In part II, we design a continuous counter part of the Graham Scan convex hull algorithms that computes the tight convex envelope of degree-n univeraite polynomial in O(n³ + n log²n log b + nb²) with respect to an interval domain, and updates in O(nb²) with respect to a new interval domain, where 2 ^b is the relative precision for float point arithmetic. Such algorithm relies on properties of convex functions for its prooof of correctness, and can be used to construct high quality convex relaxations for Generalized Additional Model (G M) with monotone link functions.

43 pages

Thesis Committee:
Barnabás Póczos (Chair)
Jason Li

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu