New query lower bounds for submodular function minimization

Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, S. Matthew Weinberg

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

Abstract

We consider submodular function minimization in the oracle model: given black-box access to a submodular set function f : 2[n] → R, find an element of arg minS{f(S)} using as few queries to f(·) as possible. State-of-the-art algorithms succeed with Õ(n2) queries [13], yet the best-known lower bound has never been improved beyond n [6]. We provide a query lower bound of 2n for submodular function minimization, a 3n/2 − 2 query lower bound for the non-trivial minimizer of a symmetric submodular function, and a n2 query lower bound for the non-trivial minimizer of an asymmetric submodular function. Our 3n/2 − 2 lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a 3n/2 − 2 cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than n + 1 for s-t mincut, even in a directed, weighted graph.

Original languageEnglish (US)
Title of host publication11th Innovations in Theoretical Computer Science Conference, ITCS 2020
EditorsThomas Vidick
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771344
DOIs
StatePublished - Jan 2020
Event11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States
Duration: Jan 12 2020Jan 14 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume151
ISSN (Print)1868-8969

Conference

Conference11th Innovations in Theoretical Computer Science Conference, ITCS 2020
CountryUnited States
CitySeattle
Period1/12/201/14/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Min cut
  • Query lower bounds
  • Submodular functions

Fingerprint Dive into the research topics of 'New query lower bounds for submodular function minimization'. Together they form a unique fingerprint.

Cite this