Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A polynomial time 12-approximation algorithm for restricted Santa Claus
  problem   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\cite{bansal}. We then apply the
analysis of Asadpour \textit{et al.} \cite{AFS,AFS2} to show that the clustered
instance has an integer solution which is at least $\frac{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 $\frac{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 $\frac{1}{6}$ times the optimum. We then use the well known
rounding technique due to Bezakova and Dani \cite{bezakova} on the 12-gap
instance to get our 12-approximate solution.

32
The categories of this paper are: atom-ph
21
The categories of this paper are: adap-org
14
The categories of this paper are: math-ph
18
The categories of this paper are: econ
20
The categories of this paper are: acc-phys
0
The categories of this paper are: hep-ph
7
The categories of this paper are: hep-th
26
The categories of this paper are: bayes-an
19
The categories of this paper are: eess
3
The categories of this paper are: physics
6
The categories of this paper are: astro-ph
5
The categories of this paper are: gr-qc
10
The categories of this paper are: q-bio
12
The categories of this paper are: nucl-th
4
The categories of this paper are: cond-mat
15
The categories of this paper are: nucl-ex