Min-max partitioning of hypergraphs and symmetric submodular functions

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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).

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery
Pages1026-1038
Number of pages13
ISBN (Electronic)9781611976465
StatePublished - 2021
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: Jan 10 2021Jan 13 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Country/TerritoryUnited States
CityAlexandria, Virtual
Period1/10/211/13/21

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Min-max partitioning of hypergraphs and symmetric submodular functions'. Together they form a unique fingerprint.

Cite this