English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we consider the restricted case of the problem and improve thecurrent best approximation ratio by presenting a polynomial time12-approximation algorithm using linear programming and semi-definiteprogramming. Our algorithm starts by solving the configuration LP and uses theoptimum value to get a 12-gap instance. This is then followed by the well-knownclustering technique of Bansal and Sviridenko\cite{bansal}. We then apply theanalysis of Asadpour \textit{et al.} \cite{AFS,AFS2} to show that the clusteredinstance has an integer solution which is at least $\frac{1}{6}$ times the bestpossible value, which was computed by solving the configuration LP. To findthis solution, we formulate a problem called the Extended Assignment Problem,and formulate it as an LP. We then, show that the associated polytope isintegral 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 quadraticprogram that we introduce to select one machine from each cluster, and then weshow that the resulting instance has an Assignment LP fractional solution ofvalue at least $\frac{1}{6}$ times the optimum. We then use the well knownrounding technique due to Bezakova and Dani \cite{bezakova} on the 12-gapinstance to get our 12-approximate solution.

A polynomial time 12-approximation algorithm for restricted Santa Claus problem