Vi anser Hypergraph Multiway Partition problem (Hyper-MP). Ingången består av en kant-viktad hypergraf G = (V, E) och k hörn s 1,. .., s k terminaler. En flervägspartition av hypergrafen är en partition (eller märkning) av hörnen i G till k-uppsättningar är hypergrafskärningsfunktionen. Hyper-MP problemet ber om en multiway partition av lägsta kostnad. Vårt huvudsakliga resultat är en 4/3 approximation för Hyper-MP-problemet på 3-uniform hypergrafer, vilket är den första förbättringen jämfört med (1,5‐1/k) approximationen av [5]. Algoritmen kombinerar Calinescu et al:s avrundningsstrategi med ett enda tröskelvärde. [3] med avrundning strategi Kleinberg och Tardos [8], och det paralleller den senaste algoritmen av Buchbinder et al. [2] för problemet Graph Multiway Cut, vilket är ett specialfall. På den negativa sidan visar vi att KT-avrundningsschemat [8] och det exponentiella avrundningsschemat [2] inte kan bryta (1,5–1/k)-barriären för godtyckliga hypergrafer. Vi ger en familj av fall för vilka båda avrundningssystem har en approximationsgrad som avgränsas nedan av  och därmed diagram Multiway Cut avrundning system kanske inte är tillräckligt för Hyper-MP problem när den maximala hyperkanten storlek är stor. Vi noterar att dessa fall har k =  på (log n). k i=1 w(σ(A i )), där w(σ(· )) är hypergraph cut funktion 1. Hyper-MP problemet ber om en multiway partition av lägsta kostnad. Vi parameteriserar också problemet av den maximala kardinaliteten av en hyperedge, betecknad av c; den välstuderade Graph Multiway Cut problemet är specialfallet för vilken c = 2. 1 För varje uppsättning A V av hörn, använder vi δ(A) för att beteckna uppsättningen av alla hyperedges lämnar A, dvs., hyperedges e E sådan att A e och (V − A) e är båda icke-tomma. Vi använder w(δ(A)) för att beteckna den totala vikten av de kanter som lämnar A, dvs. w(δ(A)) = e och δ(A) w(e).
Ene och Nguyen REF studerade multiway-partitionsproblemen i hypergrafen (generaliserar multiway-partitionsproblemet) och gav en 4/3-approximationsalgoritm.
From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?
{'venue': 'ESA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}