New Query Lower Bounds for Submodular Function Minimization

DOI10.4230/LIPIcs.ITCS.2020.64OpenAlexW3003509205MaRDI QIDQ5875771

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

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1911.06889

zbMATH Keywords

submodular functionsmin cutquery lower bounds

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Algorithms that access the input via queries ⋮ Almost optimal query algorithm for hitting set using a subset query

This page was built for publication: New Query Lower Bounds for Submodular Function Minimization