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