Abstract Graph clustering är ett viktigt problem med applikationer för bioinformatik, samhällsupptäckt i sociala nätverk, distribuerade datorer med mera. Större delen av forskningen inom detta område har inriktats på kluster med hjälp av separata kluster, men många verkliga datauppsättningar har till sin natur överlappande kluster. Vi jämför överlappande och icke-överlappande kluster i grafer i samband med att minimera deras ledning. Det är känt att möjligheten att låta kluster överlappa ger bättre resultat i praktiken. Vi bevisar att överlappande kluster kan vara betydligt bättre än icke-överlappande kluster med avseende på ledning, även i en teoretisk miljö. För att minimera den maximala ledningen över kluster, ger vi exempel som visar att tillåta överlappningar kan ge betydligt bättre kluster, nämligen en som har mycket mindre optimal. Dessutom för min-max variant, den överlappande versionen medger en enkel approximation algoritm, medan vår algoritm för den icke-överlappande versionen är komplex och ger en sämre approximation förhållande på grund av förekomsten av ytterligare begränsning. Något förvånande, för problemet med att minimera summan av uppföranden, upptäckte vi att tillåta överlappning inte hjälper. Vi visar hur man tillämpar en allmän teknik för att omvandla alla överlappande kluster till en icke-överlappande en med endast en blygsam ökning av summan av con-kanals. Denna ocrossing teknik är av oberoende intresse och kan hitta ytterligare tillämpningar i framtiden. Vi ser detta arbete som ett steg mot en rigorös jämförelse av överlappande och icke-överlappande kluster och hoppas att det stimulerar ytterligare forskning på detta område.
En av författarna har nyligen studerat de liknande problemen med överlappande kluster och etablerat både komplexa resultat och nya polylogaritmiska approximationsalgoritmer för dessa problem REF.
On the Advantage of Overlapping Clusters for Minimizing Conductance
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}