A Faster Scaling Algorithm for Minimizing Submodular Functions

DOI10.1137/S0097539701397813MaRDI QIDQ4706234zbMATH OpenFDO

Authors Satoru Iwata

Publication date 19 June 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539701397813

zbMATH Keywords

algorithmsubmodular functiondiscrete optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 2086909
• scientific article; zbMATH DE number 7051294
• Improved algorithms for submodular function minimization and submodular flow

Cited in

(26)

• The expressive power of valued constraints: Hierarchies and collapses
• Buyer selection and service pricing in an electric fleet supply chain
• Submodular function minimization
• Minimizing convex functions with rational minimizers
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Minimizing a sum of submodular functions
• A scaling algorithm for optimizing arbitrary functions over vertices of polytopes
• Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
• The median partition and submodularity
• A faster strongly polynomial time algorithm for submodular function minimization
• The expressive power of binary submodular functions
• Submodular function minimization under a submodular set covering constraint
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A strongly polynomial algorithm for line search in submodular polyhedra
• A capacity scaling algorithm for M-convex submodular flow
• Geometric rescaling algorithms for submodular function minimization
• Theory of principal partitions revisited
• Rank-width: algorithmic and structural results
• A polynomial algorithm for a class of 0-1 fractional programming problems involving composite functions, with an application to additive clustering
• Improved algorithms for submodular function minimization and submodular flow
• scientific article; zbMATH DE number 2086909 (Why is no real title available?)
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Hierarchical design of fast minimum disagreement algorithms
• A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
• The Expressive Power of Valued Constraints: Hierarchies and Collapses
• Minimization of locally defined submodular functions by optimal soft arc consistency

This page was built for publication: A Faster Scaling Algorithm for Minimizing Submodular Functions

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