Vi studerar approximabiliteten av multiway partitionering problem, som exempel inkluderar Multiway Cut, Node-viktade Multiway Cut, och Hypergraph Multiway Cut. Vi undersöker dessa problem utifrån två möjliga generaliseringar: som Min-CSP, och som Submodulära Multiway Partition problem. Dessa två generaliseringar leder till två naturliga avkopplingar, Basic LP, och Lovász avkoppling. Basic LP är generellt starkare än Lovász-avslappningen, men växer exponentiellt med min-CSP. Avslappningarna sammanfaller i vissa fall som Multiway Cut där de båda är likvärdiga med CKR avslappning. Vi visar att Lovász-avkopplingen ger en (2 − 2/k)-approximation för Submodulär multivägspartition med k-terminaler, vilket förbättrar en ny 2-accession [4]. Vi bevisar att denna faktor är optimal i två bemärkelser: (1) A (2 − 2/k −  och)-uppskattning för Submodulär flervägspartition med k-terminaler skulle kräva exponentiellt många värdefrågor. (2) För Hypergraph Multiway Cut och Node-viktade Multiway Cut med k-terminaler, båda specialfall av Submodulär Multiway Partition, visar vi att en (2 − 2/k −  på)-uppskattning är NP-hård, förutsatt att den unika Games Conjecture. Båda våra hårdhetsresultat är mer allmänna: (1) Vi visar att begreppet symmetri gap, som tidigare använts för submodulära maximeringsproblem [24, 8], också innebär hårdhet resultat för submodulära minimering problem. (2) Under förutsättning att det unika spelen antas, visar vi att Basic LP ger en optimal approximation för varje Min-CSP som inkluderar Non-Equal predicate. Slutligen ansluter vi de två hårdhetsteknikerna genom att bevisa att integrality gapet i Basic LP sammanfaller med symmetri gapet i multilinjär avkoppling (för ett relaterat fall). Detta visar att uppkomsten av samma hårdhet tröskel för en Min-CSP och den relaterade submodulära minimering problem är inte en tillfällighet.
Detta förbättrades ytterligare till en (2 − 2 k ) - approximation kort efter av Ene et al. Hoppa över det.
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}