Research
I am interested in theoretical computer science, specifically approximation algorithms
for NP-hard problems, hardness of approximation, and theory of Computation. Recently I have been working on the following two problems:
-
Minimum Weight Triangulation:The best known result for
approximating MWT is a constant-factor approximation. Levcopoulous and Kraznaric showed
that a triangulation of the total length within a constant factor of the MWT can be computed in
polynomial time for any point set. Their algorithm is a modification of the
greedy triangulation. However, the constant shown in their paper is not explicitly calculated and it could be relatively large. Thus, it would be desirable to improve the approximation constant which can be achieved in polynomial time. We proposed an integer linear programming formulation of the problem. The integer linear program can be relaxed and solved to achieve a fractional solution. We have proved upper bounds on the integrality gap of the LP-relaxation in some special cases of the problem,and we conjecture that the integrality ratio is less than 2. The integrality ratio of the worst known instance of the problem is no more than 7/6. Our next goal is to upper bound the gap in the general case.
-
Multiway Cut: For the k-way cut problem, Calinescu et al. described an (1.5-1/k)-approximation algorithm based on the geometric embedding of graph's vertices into Rk.
Karger et al. showed the integrality ratio of the relaxation for k=3 is exactly 12/11, and showed an upper bound of 1.3438 for general k. However, this upper bound is not tight. We have been working on the case of k=4 to find a better upper bound on the integrality gap of the relaxation.
|