Technical Report MSC-2021-28

Title: The Metric Relaxation for 0-Extension Admits an Ω(log^2/3)(k) Gap
Authors: Nitzan Tur
Supervisors: Roy Schwartz
PDFCurrently accessibly only within the Technion network
Abstract: 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$ special vertices called terminals, and a semi-metric $D$ over $T$.

The goal is to assign every non-terminal vertex to a terminal while minimizing the sum over all edges of the weight of the edge multiplied by the distance in $D$ between the terminals to which the endpoints of the edge are assigned. $0$-Extension admits two known algorithms, achieving approximations of $O(\log{k})$ [Clinescu-Karloff-Rabani {\em SICOMP} '05] and $O(\log{k}/\log{\log{k}})$ [Fakcharoenphol-Harrelson-Rao-Talwar {\em SODA} '03].

Both known algorithms are based on rounding a natural linear programming relaxation called the metric relaxation, in which $D$ is extended from $T$ to the entire of $V$.

The current best known integrality gap for the metric relaxation is $\Omega (\sqrt{\log{k}})$.

In this work we present an improved integrality gap of $\Omega(\log^{\nicefrac[]{2}{3}}k)$ for the metric relaxation. Our construction is based on the randomized extension of one graph by another, a notion that captures lifts of graphs as a special case and might be of independent interest.

Inspired by algebraic topology, our analysis of the gap instance is based on proving no continuous section (in the topological sense) exists in the randomized extension.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2021
To the main CS technical reports page

Computer science department, Technion