A polynomial time 12-approximation algorithm for restricted Santa Claus problem
share
In this paper, we consider the restricted case of the problem and improve the current best approximation ratio by presenting a polynomial time 12-approximation algorithm using linear programming and semi-definite programming. Our algorithm starts by solving the configuration LP and uses the optimum value to get a 12-gap instance. This is then followed by the well-known clustering technique of Bansal and Sviridenko<cit.>. We then apply the analysis of Asadpour et al. <cit.> to show that the clustered instance has an integer solution which is at least 1/6 times the best possible value, which was computed by solving the configuration LP. To find this solution, we formulate a problem called the Extended Assignment Problem, and formulate it as an LP. We then, show that the associated polytope is integral and gives us an fractional solution of value at least 1/6 times the optimum. From this solution we find a solution to a new quadratic program that we introduce to select one machine from each cluster, and then we show that the resulting instance has an Assignment LP fractional solution of value at least 1/6 times the optimum. We then use the well known rounding technique due to Bezakova and Dani <cit.> on the 12-gap instance to get our 12-approximate solution.
READ FULL TEXT