A maximum density subset problem and its algorithm with appropriate binary search

This paper deals with a problem of finding maximum density subsets on a set system, which is a generalization of a maximum density subgraph problem. Some examples show a set system model detects communities different from a graph model, which says that a generalization of a density subgraph problem and its algorithm to on a set system is important. By combining approximate binary search and a maximum flow algorithm, an efficient algorithm for finding maximum density subsets is developed. We also discuss how a framework of the proposed approximate binary search algorithm can be applied for a weighted version of the problem and for a maximum mean cut problem.