Vi studerar algoritmer för SUBMODULAR MUL-TIWAY PARTITION problem (SUB-MP). Ett exempel på SUB-MP består av en ändlig mark uppsättning V, en delmängd S = {s1, s2,. .., s k }  på V k element kallas terminaler, och en icke-negativ submodulär uppsättning funktion f : 2 V → R+ på V tillhandahålls som ett värde oracle. Målet är att partitionen V i k uppsättningar A1,. .., A k för att minimera k i=1 f (Ai) sådan att för 1 ≤ i ≤ k, si  till Ai. SUB-MP generaliserar några välkända problem som MULTIWAY CUT problem i grafer och hypergrafer, och NODE-WEGHED MULTIWAY CUT problem i grafer. SUB-MP för godtyckliga submodulära funktioner (i stället för symmetriska funktioner) övervägdes av Zhao, Nagamochi och Ibaraki [29]. Tidigare algoritmer baserades på girig uppdelning och uppdelning och erövra strategier. I det senaste arbetet [5] föreslog vi en konvex-programmering avkoppling för SUB-MP baserat på Lovász-utvidgningen av en submodulär funktion och visade dess tillämplighet i vissa specialfall. I detta dokument får vi följande resultat för godtyckliga submodulära funktioner via denna avkoppling. • En 2- approximation för SUB-MP. Detta förbättrar (k − 1) approximationen från [29]. • A (1,5‐ 1 k ) - approximation för SUB-MP när f är symmetrisk. Detta förbättrar 2( 1 − 1 k) - approximationen från [23], [29].
Dessa problem övervägdes av Zhao, Nagamochi och Ibaraki [31] som analyserade giriga fragmenterande algoritmer, och mer nyligen av Chekuri och Ene REF som använde en Lovász-extension baserad konvex avkoppling.
Approximation Algorithms for Submodular Multiway Partition
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}