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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We design approximation algorithms for Unique Games when the constraint graphadmits good low diameter graph decomposition. For the ${\sf Max2Lin}_k$ problemin $K_r$-minor free graphs, when there is an assignment satisfying$1-\varepsilon$ fraction of constraints, we present an algorithm that producesan assignment satisfying $1-O(r\varepsilon)$ fraction of constraints, with theapproximation ratio independent of the alphabet size. A corollary is animproved approximation algorithm for the ${\sf MaxCut}$ problem for $K_r$-minorfree graphs. For general Unique Games in $K_r$-minor free graphs, we provideanother algorithm that produces an assignment satisfying $1-O(r\sqrt{\varepsilon})$ fraction of constraints.  Our approach is to round a linear programming relaxation to find a minimumsubset of edges that intersects all the inconsistent cycles. We show that it ispossible to apply the low diameter graph decomposition technique on theconstraint graph directly, rather than to work on the label extended graph asin previous algorithms for Unique Games. The same approach applies when theconstraint graph is of genus $g$, and we get similar results with $r$ replacedby $\log g$ in the ${\sf Max2Lin}_k$ problem and by $\sqrt{\log g}$ in thegeneral problem. The former result generalizes the result of Gupta-Talwar forUnique Games in the ${\sf Max2Lin}_k$ case, and the latter result generalizesthe result of Trevisan for general Unique Games.

Approximating Unique Games Using Low Diameter Graph Decomposition