Linearly representable submodular functions: an algebraic algorithm for minimization

DOI10.4230/LIPICS.ICALP.2020.61MaRDI QIDQ6842512zbMATH OpenFDO

Authors Rohit Gurjar, Rajat Rathi

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.61

zbMATH Keywords

derandomizationparallel algorithmsalgebraic algorithmssubmodular minimization

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 4202014 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial strongly polynomial algorithm for minimizing submodular functions
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• A faster cutting plane method and its implications for combinatorial and convex optimization
• A lower bound for parallel submodular minimization
• A probabilistic remark on algebraic program testing
• Adaptive greedy approximations
• Bipartite perfect matching is in quasi-NC
• Constructing a perfect matching is in random NC
• Covering the edge set of a directed graph with trees
• Cutsets and partitions of hypergraphs
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast parallel matrix and GCD computations
• Geometric algorithms and combinatorial optimization
• Linear matroid intersection is in quasi-NC
• Matching is as easy as matrix inversion
• Maximizing Non-monotone Submodular Functions
• On submodular function minimization
• On the Number of Combinatorial Geometries
• Parameterized complexity of Vertex Cover variants
• Polynomial pass lower bounds for graph streaming algorithms
• Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
• Reducibility among combinatorial problems
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• The ellipsoid method and its consequences in combinatorial optimization
• Über höhere Kongruenzen.

This page was built for publication: Linearly representable submodular functions: an algebraic algorithm for minimization

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