The Santa Claus problem is a well known N P -hard problem in the class of resource allocation
problems. In this problem, we are given a set J of jobs to be allocated among a set of machines
M in such a way that machine i on allocating job j gets size p ij . We are required to allocate the
jobs in J among the machines in M so as to maximise the minimum total size on all machines.
It has been proved by Bansal and Sviridenko that the general case of the problem has unbounded
integrality gap. Hence researches focuss on the Restricted Santa Claus problem suggested by Bansal
and Sviridenko, in which p ij ∈ {0, p j } for each job j. It has been proved by Asadpour, Feige and
Saberi that the resticted Santa Claus problem has constant integrality gap and the best known
polynomial algorithm for the problem has an approximation ratio of 4.
We study the restricted Santa Claus problem in detail and derive approximation algorithms
which use the Machine Job Clustering technique suggested by Bansal and Sviridenko as the basic
platform. The best polynomial time algorithm that uses this clustering technique as the starting
point is the one with approximation ratio 13 due to Annamalai Chidambaram et al.. By classifying
the machines into upper class machines and middle class machines and applying this machine job
clustering technique in on upper class machines, we derive the following result.
• There exists a polynomial time 12- approximation algorithm for the restricted Santa Claus
problem that uses the Machine Job Clustering technique.
In addition to the fact that our approximation algorithm is an improvement over the existing
machine job clustering based approximation algorithms for the problem, the proposed algorithm
has the following other features.
1. Our algorithm uses Linear Programming and Semidefinite Programming, This is the first
algorithm that uses Semidefinite Programming to solve Santa Claus problem.
2. Our algorithm is conceptually simple and is yet another witness to the effectiveness of the
configuration LP to obtain improved approximation ratios.
3. Our algorithm neither uses any alternating tree technique as used in the super polynomial
time 4-approximation algorithm due to Adaspour, Feige and Saberi nor apply any greedy
techniques such as Lazy Local Search and Greedy Players as used in the 13-approximation
algorithm.