New Query Lower Bounds for Submodular Function Minimization

DOI10.4230/LIPICS.ITCS.2020.64MaRDI QIDQ5875771zbMATH OpenOpenAlexFDO

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

Publication date 3 February 2023

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

zbMATH Keywords

min cutquery lower boundssubmodular functions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Subquadratic submodular function minimization
• Towards minimizing k-submodular functions
• On submodular function minimization
• Algorithms and lower bounds for submodular cuts and approximating submodular functions
• Submodular maximization with nearly optimal approximation, adaptivity and query complexity
• Submodular function minimization and related topics
• Submodular function minimization
• Submodular function minimization
• Submodular functions: optimization and approximation
• A faster strongly polynomial time algorithm for submodular function minimization

Cited in

(6)

• Almost optimal query algorithm for hitting set using a subset query
• On the cut-query complexity of approximating max-cut
• Learning spanning forests optimally in weighted undirected graphs with CUT queries
• A query algorithm for learning a spanning forest in weighted undirected graphs
• Learning partitions using rank queries
• Algorithms that access the input via queries

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875771)