Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions
Karthekeyan Chandrasekaran, Chandra Chekuri · Society for Industrial and Applied Mathematics eBooks · 2021
We consider the complexity of minmax partitioning of graphs, hypergraphs and (symmetric) submodular functions. Our main result is an algorithm for the problem of partitioning the ground set of a given symmetric submodular function f : 2V → ℝ into k non-empty parts V1, V2, …, Vk to minimize . Our algorithm runs in time, where n = |V| and T is the time to evaluate f on a given set; hence. this yields a polynomial time algorithm for any fixed k in the evaluation oracle model. As an immediate corollary, for any fixed k, there is a polynomial-time algorithm for the problem of partitioning the vertex set of a given hypergraph H = (V, E) into k non-empty parts to minimize the maximum capacity of the parts. The complexity of this problem. termed Minmax-Hypergraph-k-Part, was raised by Lawler in 1973 [16]. In contrast to our positive result, the reduction in [6] implies that when k is part of the input, Minmax-Hypergraph-k-Part is hard to approximate to within an almost polynomial factor under the Exponential Time Hypothesis (ETH).