Lagrangian avkoppling har använts i stor utsträckning i utformningen av approximation algoritmer. I detta dokument studeras dess styrkor och begränsningar när de tillämpas på Partial Cover. Vi visar att för Partial Cover i allmänhet ingen algoritm som använder Lagrangian avkoppling och en Lagrangian Multiplier Preserving (LMP) α-uppskattning som en svart låda kan ge en approximationsfaktor bättre än 4 3 α. Detta matchar den övre gränsen som ges av Könemann et al. (ENS 2006, sidorna 468–479). Inför denna begränsning studerar vi en specifik, men ändå bred klass av att täcka problem: Partiell Total Balanserad Täckning. Genom att noggrant analysera LMP-algoritmens inre funktion kan vi ge en nästan tight karakterisering av integralititetsklyftan i problemets normala linjära avslappning. Som en följd av detta får vi förbättrade approximationer för den partiella versionen av Multicut och Path Hitting på träd, Rektangle Stabbing, och Set Cover med ρ-Blocks. 2000 ACM Ämnesklassificering: G.2.1.
Nyligen, Mestre REF har visat att i allmänhet ingen algoritm som använder en Lagrangian multiplikator bevara α- approximation algoritm som en svart låda kan ge en approximationsfaktor bättre än
LAGRANGIAN RELAXATION AND PARTIAL COVER
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}