Many optimization problems arise in an online setting, where inputs arrive sequentially and decisions must be made without knowledge of the future. This thesis studies two fundamental online optimization problems: facility location and bipartite matching.

 

For online facility location, we investigate two natural variants involving weighted requests and congestion. We present optimal competitive variants for both of these variants.

 

For online bipartite matching, we obtain several new results. We prove that, for degree-2 instances, the folklore Half-Half algorithm achieves the optimal competitive ratio of approximately 0.7178, showing that no randomized algorithm can do better. We also present a new WaterLevel-based view of optimal deterministic fractional edge-weighted matching, and analyze a candidate online correlated selection algorithm, obtaining improved guarantees over single intervals.

 

The talk will present the key ideas behind these results and the techniques used in their analysis.