Before revision: We consider the restricted case of the Santa Claus problem and improve the current best approximation ratio by presenting a polynomial time 12-approximation algorithm using linear programming and novel quadratic program that we consider .
After revision: We consider the restricted case of the Santa Claus problem and improve the current best approximation ratio by presenting a polynomial time 12-approximation algorithm using linear programming and semi-definite programming .