We study the problem of learning to partition users into groups, where one must learn the compatibilities between the users to achieve optimal groupings. We define four natural objectives that optimize for average and worst case compatibilities and propose new algorithms for adaptively learning optimal groupings. When we do not impose any structure on the compatibilities, we show that the group formation objectives considered are @math hard to solve and we either give approximation guarantees or prove inapproximability results. We then introduce an elegant structure, namely that of , that makes many of these problems polynomial time solvable. We explicitly characterize the optimal groupings under this structure and show that the optimal solutions are related to and partitions, well-studied in the psychology literature. For one of the four objectives, we show @math hardness under the score structure and give a @math approximation algorithm for which no constant approximation was known thus far. Finally, under the score structure, we propose an online low sample complexity PAC algorithm for learning the optimal partition. We demonstrate the efficacy of the proposed algorithm on synthetic and real world datasets.
There is one class of graph partitioning problems that come with size restrictions, namely, the Graph Tree Partitioning Problem @cite_10 , where the objective is to partition a graph into equal size subsets, such that the weight of the spanning tree on each subset is either as high as possible (max-min) or as low as possible (min-max), or, the sum of the weights of the spanning trees are either as high (max-sum), or, as low (min-sum) as possible. Though these objectives are closely related to ours, they are not exactly the same problems.
@cite_10
2098322943
We prove that any graph excluding Kr as a minor has can be partitioned into clusters of diameter at most Δ while removing at most O(r Δ) fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who building on the work of Klein, Plotkin and Rao gave a partitioning that required to remove O(r2 Δ) fraction of the edges. Our result is obtained by a new approach that relates the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops and robbers game on graphs excluding a fixed minor, can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter O(r) and strong-diameter partitions with padding parameter O(r2) for Kr-free graphs, O(k) for treewidth-k graphs, and O(log g) for graphs with genus g.