论文标题
限制圣诞老人问题的多项式时间12-鉴定算法
A polynomial time 12-approximation algorithm for restricted Santa Claus problem
论文作者
论文摘要
在本文中，我们通过使用线性编程和半明确编程来提出多项式时间12-透明度算法来考虑问题的受限情况，并提高当前最佳近似比。我们的算法首先求解配置LP，并使用最佳值来获得12个存在的实例。然后是Bansal和Sviridenko \ cite {Bansal}的众所周知的聚类技术。然后，我们应用了Asadpour \ textit {等} \ cite {afs，afs2}的分析，以表明群集实例具有一个整数解决方案，该解决方案至少为$ \ frac {1} {6} {6} $ timeral，最佳值，这是通过求解配置lp来计算的。为了找到此解决方案，我们制定了一个称为扩展分配问题的问题，并将其作为LP提出。然后，我们证明关联的多层是不可或缺的，并为我们提供了一个值的分数解决方案，至少$ \ frac {1} {6} {6} $ times the Optimum the Optimum。从该解决方案中，我们找到了一个新的二次程序的解决方案，我们介绍了该解决方案，从每个群集中选择一台计算机，然后我们证明了结果实例具有一个分配的LP分数值，至少$ \ frac {1} {1} {6} {6} $ timeral the Optimum。然后，由于Bezakova和Dani \ cite {Bezakova}，我们使用众所周知的圆形技术，以获取我们的12个同一解决方案。
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.
