Approximating Max k-Uncut via LP-rounding plus greed, with applications to Densest k-Subgraph

The problem arose from the study of homophily of large-scale networks. Given an -vertex undirected graph with nonnegative weights defined on edges and a positive integer , the problem asks to find a partition of such that the total weight of edges that are cut is maximized. This problem is the complement of the classic problem, and was proved to have surprisingly rich connection to the problem. In this paper, we give an approximation algorithm for using a non-uniform approach combining LP-rounding and the greedy strategy. The algorithm partitions the vertices of into at least parts in expectation, and achieves a good expected approximation ratio .