M.Sc Thesis

M.Sc StudentTur Nitzan
SubjectThe Metric Relaxation for 0-Extension Admits an
Omega(log (2/3)k) Gap
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Roy Schwartz
Full Thesis textFull thesis text - English Version


We consider the 0-Extension problem, where we are given an undirected graph G=(V,E) equipped with non-negative edge weights w: E -> R, a collection T=t_1,?,t_k of k special vertices from V 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)) in Calinescu-Karloff-Rabani (SICOMP '05) and O(log(k)/log(log(k))) in Fakcharoenphol-Harrelson-Rao-Talwar (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 Ω(log^1/2)(k).

In this work we present an improved integrality gap of Ω(log^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.