Vi studerar begreppet stabilitet och perturbation resiliens som infördes av Bilu och Linial (2010) och Awasthi, Blum och Sheffet (2012). Ett kombinatoriskt optimeringsproblem är α-stabilt eller α-perturbation-resilient om den optimala lösningen inte förändras när vi stör alla parametrar av problemet med en faktor som högst α. I den här artikeln ger vi förbättrade algoritmer för stabila fall av olika kluster- och kombinatoriska optimeringsproblem. Vi bevisar också flera hårdhetsresultat. Vi rst ger en exakt algoritm för 2-perturbation motståndskraftiga fall av klusterproblem med naturliga center-baserade mål. Klassen av klusterproblem med naturliga center-baserade mål inkluderar sådana problem som k-medel, k-median och k-center. Vårt resultat förbättras på resultatet av Balcan och Liang (2016), som gav en algoritm för att klunga 1 + 2  och 2,41 perturbationresilienta instanser. Vårt resultat är tight i den meningen att ingen polynom tid algoritm kan lösa (2 − ε )-perturbation motståndskraftiga fall av k-center om inte N P = RP, som visades av Balcan, Haghtalab och White (2016). Vi ger sedan en exakt algoritm för (2 − 2/k )-stabila instanser av Minimum Multiway Cut med k-terminaler, förbättra det tidigare resultatet av Makarychev, Makarychev, och Vijayaraghavan (2014), som gav en algoritm för 4-stabila fall. Vi ger också en algoritm för (2 − 2/k + δ ) - svagt stabila instanser av Minimum Multiway Cut. Slutligen visar vi att det inte finns några robusta polynom-tidsalgoritmer för n 1−ε -stabila fall av Set Cover, Minimum Vertex Cover och Min 2-Horn Deletion (om inte P = N P). • Teori för beräkning → Anläggningens läge och klusterbildning; KEYWORDS perturbation resilience och stabilitet, k-median, k-medel ACM Referensformat: Haris Angelidakis, Konstantin Makarychev och Yury Makarychev. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning.
Nyligen, Angelidakis m.fl. REF, gav en enande algoritm som ger exakt lösning för 2-perturbation motståndskraftiga fall av klusterproblem med centerbaserade mål.
Algorithms for stable and perturbation-resilient problems
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}