Algorithms and lower bounds for submodular cuts and approximating submodular functions

MaRDI QIDQ2999659zbMATH OpenFDO

Authors Zoya Svitkina, Lisa Fleischer

Publication date 16 May 2011

zbMATH Keywords

lower boundsapproximabilitysubmodular balanced cut problemsubmodular sparsest cut problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• scientific article; zbMATH DE number 7051222
• Maximizing Non-monotone Submodular Functions
• Submodular functions: optimization and approximation

Cited in

(5)

• New Query Lower Bounds for Submodular Function Minimization
• Improving graph partitions using submodular functions.
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Approximating submodular \(k\)-partition via principal partition sequence
• scientific article; zbMATH DE number 5888315 (Why is no real title available?)

This page was built for publication: Algorithms and lower bounds for submodular cuts and approximating submodular functions

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