The first approach to design polynomial time approximation algorithms for the restricted assignment case of the Santa Claus problem used a clustering technique due to Bansal and Sviridenko (The Santa Claus Problem, 2006), which we call BS-Clustering. In this work, we present a polynomial time \(12+\epsilon\) -approximation algorithm for any \(\epsilon \in (0,1)\) using BS-Clustering and geometric programming to solve this problem. While our approach does not achieve the current best \(4+\epsilon\) -algorithm ( Davies et al., A Tale of Santa Claus, Hypergraphs and Matroids, 2020) due to its inherent rounding errors, it sheds light on the effectiveness of BS-Clustering and geometric programming in solving Max-Min fair allocation problems. To the best of our knowledge, this is the first result in which a nonlinear programming technique such as geometric programming is used to design a polynomial time constant factor approximation algorithm for the restricted assignment case of the Santa Claus problem.
