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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We consider the $0$-Extension problem, where we are given an undirected graph$\mathcal{G}=(V,E)$ equipped with non-negative edge weights $w:E\rightarrow\mathbb{R}^+$, a collection $ T=\{ t_1,\ldots,t_k\}\subseteq V$ of $k$ specialvertices called terminals, and a semi-metric $D$ over $T$. The goal is toassign every non-terminal vertex to a terminal while minimizing the sum overall edges of the weight of the edge multiplied by the distance in $D$ betweenthe terminals to which the endpoints of the edge are assigned. $0$-Extensionadmits two known algorithms, achieving approximations of $O(\log{k})$[C{\u{a}}linescu-Karloff-Rabani SICOMP '05] and $O(\log{k}/\log{\log{k}})$[Fakcharoenphol-Harrelson-Rao-Talwar SODA '03]. Both known algorithms are basedon rounding a natural linear programming relaxation called the metricrelaxation, in which $D$ is extended from $T$ to the entire of $V$. The currentbest known integrality gap for the metric relaxation is $\Omega(\sqrt{\log{k}})$. In this work we present an improved integrality gap of$\Omega(\log^{\frac{2}{3}}k)$ for the metric relaxation. Our construction isbased on the randomized extension of one graph by another, a notion thatcaptures lifts of graphs as a special case and might be of independentinterest. Inspired by algebraic topology, our analysis of the gap instance isbased on proving no continuous section (in the topological sense) exists in therandomized extension.

The Metric Relaxation for $0$-Extension Admits an $\Omega(\log^{2/3}{k})$ Gap