Possible Research Problems

Approximation on Graphs

• Generalize the EPTAS on disk graphs to general geometric intersection graphs with a 'fatness' parameter.
• Generalize disk graphs to \((\alpha,\beta)\)-realizable disk graphs and check the hardness of approximating feedback set and approximating weighted vertex cover.

Approximating Matrix Permanent

• Determine the optimal approximation ratio for Hermitian PSD matrix permanent
• Find a convex optimization version of the combinatorial algorithm described in here