Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

The Metric Relaxation for 0-Extension Admits an Omega(log²⸍³k) Gap
event speaker icon
Nitzan Tur (M.Sc. Thesis Seminar)
event date icon
Wednesday, 30.12.2020, 12:30
event location icon
Zoom, Meeting ID: 954 7347 4134, Password: 5-digit Technion Zip Code
event speaker icon
Advisor: Dr. Roy Schwartz
We consider the 0-Extension problem, where we are given an undirected graph G=(V,E) equipped with non-negative edge weights w: E→ℝ+, a collection T={t1,…,tk}⊆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(logk) [Călinescu-Karloff-Rabani SICOMP ’05] and O(logk/loglogk) [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 entirety of V. The current best known integrality gap for the metric relaxation is Ω(√logk). In this work we present an improved integrality gap of Ω(log2/3k) 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. More details.