Alladi Ramakrishnan Hall

(PhD Thesis Defense) Approximation Algorithms for Stochastic Matchings and Independent Sets

Joydeep Mukherjee

IMSc, HBNI

In this thesis we present improved approximation algorithms for
the stochastic matching problem where the input is a stochastic
subgraph of an edge-weighted graph
probed under patience constraints on vertices.

We also present improved results on efficiently approximating
the maximum independent sets in geometric intersection graphs
of special types called $B_1, B_2$-VPG graphs.