On submodular function minimization

DOI10.1007/BF02579361zbMath0647.05018DBLPjournals/combinatorica/Cunningham85OpenAlexW2015429465WikidataQ62111284 ScholiaQ62111284MaRDI QIDQ1104332

William H. Cunningham

Publication date: 1985

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579361

zbMATH Keywords

combinatorial algorithmminimizing a submodular function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Designs and configurations (05B99)

Cites Work

• Unnamed Item
• Decomposition of submodular functions
• The ellipsoid method and its consequences in combinatorial optimization
• The Partial Order of a Polymatroid Extreme Point
• Minimum cuts, modular functions, and matroid polyhedra
• Decomposition of Directed Graphs

Related Items (33)

A rounding technique for the polymatroid membership problem ⋮ On total variation minimization and surface evolution using parametric maximum flows ⋮ Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope ⋮ Submodular function minimization with submodular set covering constraints and precedence constraints ⋮ Minimum cuts in parametric networks ⋮ Decomposition Algorithm for the Single Machine Scheduling Polytope ⋮ Generalized polymatroids and submodular flows ⋮ Recognition problems for special classes of polynomials in 0-1 variables ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ On additive approximate submodularity ⋮ ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM ⋮ The holographic entropy cone from marginal independence ⋮ On the foundations and extremal structure of the holographic entropy cone ⋮ A push-relabel framework for submodular function minimization and applications to parametric optimization ⋮ Continuous limits of discrete perimeters ⋮ Efficient minimization of higher order submodular functions using monotonic Boolean functions ⋮ Paths on polymatroids ⋮ Toughness in graphs -- a survey ⋮ A strongly polynomial time algorithm for a constrained submodular optimization problem ⋮ Submodular function minimization ⋮ Dispersing obnoxious facilities on a graph ⋮ Faster algorithms for evacuation problems in networks with a single sink of small degree and bounded capacitated edges ⋮ Faster algorithms for evacuation problems in networks with a single sink of small degree and bounded capacitated edges ⋮ A faster strongly polynomial time algorithm for submodular function minimization ⋮ The base-matroid and inverse combinatorial optimization problems. ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Dispersing Obnoxious Facilities on a Graph ⋮ Unnamed Item ⋮ Minimizing symmetric submodular functions ⋮ The toughness of split graphs ⋮ A combinatorial algorithm minimizing submodular functions in strongly polynomial time. ⋮ A fully combinatorial algorithm for submodular function minimization. ⋮ A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering

This page was built for publication: On submodular function minimization