Vi betraktar problemet med att samla en samling element som bygger på parvisa bedömningar av likhet och olikhet. Bansal, Blum och Chawla (i målet 43:e FOCS), 2002, s. 238-47) gjuta problemet på följande sätt: givet en graf G vars kanter är märkta "+" (liknande) eller "−" (olika), dela upp hörnen i kluster så att antalet par korrekt (spe. felaktigt) klassificeras med avseende på inmatningsetiketten maximeras (resp. minimeras). Det är värt att studera både kompletta grafer, där varje kant är märkt, och allmänna grafer, där vissa indatakanter kanske inte har etiketter. Vi svarar på flera frågor som lämnats öppna av Bansal et al. och ge en bra översikt över kluster med kvalitativ information. Specifikt visar vi en faktor 4 approximation för minimering på kompletta grafer, och en faktor O(log n) approximation för allmänna grafer. För maximeringsversionen visades en PTAS för fullständiga grafer av Bansal et al.; Vi ger en faktor 0.7664 approximation för allmänna grafer, notera att en PTAS är osannolikt genom att bevisa APX-hårdhet. Vi bevisar också APX-hårdheten av minimering på kompletta grafer.
Observera att den senare inställningen är APX-hård REF.
Clustering with Qualitative Information
{'venue': 'FOCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}