Bootstrap, Recolor, Verify: Hierarchical Integrality Gap Instance for 0-extensionResearch Paper
Assigning network vertices to prescribed terminals is a basic form of discrete labeling. A label has a location in a metric space, and an edge pays its weight times the distance between its endpoints' labels. The optimization problem asks for a labeling of minimum total cost while keeping the terminals fixed. Researchers studying approximation algorithms…