TY - GEN

T1 - Min-max partitioning of hypergraphs and symmetric submodular functions

AU - Chandrasekaran, Karthekeyan

AU - Chekuri, Chandra

N1 - Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

N2 - 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 → R into k nonempty parts V1, V2,..., Vk to minimize maxki=1 f(Vi). Our algorithm runs in nO(k2)T 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).

AB - 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 → R into k nonempty parts V1, V2,..., Vk to minimize maxki=1 f(Vi). Our algorithm runs in nO(k2)T 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).

UR - http://www.scopus.com/inward/record.url?scp=85097809979&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85097809979&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85097809979

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1026

EP - 1038

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -