2-Catalog segmentation problem
Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna · 1999
Introduction We study the 2-Catalog Segmentation problem: Given a set I of n items and a family S = fS 1 ; S 2 ; :::; S p g of subsets of I, find C 1 ; C 2 ` I such that jC 1 j; jC 2 j r and the sum P p i=1 maxfjS i "C 1 j; jS i "C 2 jg is maximized. The problem was recently introduced by Kleinberg et al [2] and is motivated by several applications to data mining and clustering operations as detailed in [2]. Under the restriction that jS i j = \\Omega\\Gamma jIj) for each