A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions

DOI10.1145/335305.335317zbMath1296.90104arXivmath/0004089OpenAlexW1976802195WikidataQ62111282 ScholiaQ62111282MaRDI QIDQ3191976

Satoru Fujishige, Satoru Iwata, Lisa K. Fleischer

Publication date: 26 September 2014

Published in: Journal of the ACM, Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, Realizing symmetric set functions as hypergraph cut capacity, On a general framework for network representability in discrete optimization, The mixed evacuation problem, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, A new greedy strategy for maximizing monotone submodular function under a cardinality constraint, On total variation minimization and surface evolution using parametric maximum flows, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Minimum degree orderings, Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope, Image restoration with discrete constrained total variation. II: Levelable functions, convex priors and non-convex cases, Separation of partition inequalities with terminals, Supermodular functions and the complexity of MAX CSP, Maximizing a non-decreasing non-submodular function subject to various types of constraints, An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks, Optimal allocation of stock levels and stochastic customer demands to a capacitated resource, The stochastic location model with risk pooling, Reachability in arborescence packings, Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties, Minimizing submodular functions on diamonds via generalized fractional matroid matchings, Rank-width: algorithmic and structural results, Effective divisor classes on metric graphs, Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function, Testing branch-width, Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Computational geometric approach to submodular function minimization for multiclass queueing systems, Equivalence of convex minimization problems over base polytopes, FPT approximation schemes for maximizing submodular functions, Submodular functions: from discrete to continuous domains, Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint, Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms, The \(b\)-branching problem in digraphs, Improved bound for the Carathéodory rank of the bases of a matroid, A note on Schrijver's submodular function minimization algorithm., A strongly polynomial algorithm for line search in submodular polyhedra, A push-relabel framework for submodular function minimization and applications to parametric optimization, A note on the minimization of symmetric and general submodular functions, Build-pack planning for hard disk drive assembly with approved vendor matrices and stochastic demands, Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem., Stochastic block-coordinate gradient projection algorithms for submodular maximization, Is submodularity testable?, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, The complexity of soft constraint satisfaction, On the complexity of submodular function minimisation on diamonds, Hypertree width and related hypergraph invariants, Complexity of the cluster deletion problem on subclasses of chordal graphs, Partitioning posets, Algorithmic aspects of homophyly of networks, Spanning tree with lower bound on the degrees, Efficient minimization of higher order submodular functions using monotonic Boolean functions, The median partition and submodularity, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Dijkstra's algorithm and L-concave function maximization, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches, The expressive power of valued constraints: Hierarchies and collapses, Algebraic and topological closure conditions for classes of pseudo-Boolean functions, The expressive power of binary submodular functions, Global optimization for first order Markov random fields with submodular priors, Pseudo-Boolean optimization, Approximability of clausal constraints, Monadic second-order model-checking on decomposable matroids, A note on submodular function minimization by Chubanov's LP algorithm, Greedy splitting algorithms for approximating multiway partition problems, A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions, Semiconductor lot allocation using robust optimization, Coordinatewise domain scaling algorithm for M-convex function minimization, Approximating clique-width and branch-width, Minimizing a sum of submodular functions, A capacity scaling algorithm for M-convex submodular flow, Polynomial combinatorial algorithms for skew-bisubmodular function minimization, A note on submodular function minimization with covering type linear constraints, Eisenberg-Gale markets: algorithms and game-theoretic properties, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, Submodular function minimization, Differential approximation schemes for half-product related functions and their scheduling applications, The warehouse-retailer network design game, Robust monotone submodular function maximization, Complexity and approximations for submodular minimization problems on two variables per inequality constraints, Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines, Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, A faster strongly polynomial time algorithm for submodular function minimization, Symmetric submodular system: contractions and Gomory-Hu tree, Minimization of locally defined submodular functions by optimal soft arc consistency, An exact cutting plane method for \(k\)-submodular function maximization, Traveling salesman games with the Monge property, Minimizing ratio of monotone non-submodular functions, Locating and staffing service centers under service level constraints, Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties, Rank-width and vertex-minors, Discrete Newton methods for the evacuation problem, Decreasing minimization on M-convex sets: algorithms and applications, A fully combinatorial algorithm for submodular function minimization., Generalized skew bisubmodularity: a characterization and a min-max theorem, Submodular function minimization and polarity, Informative path planning as a maximum traveling salesman problem with submodular rewards, A tight analysis of the submodular-supermodular procedure, Separation of partition inequalities for the \((1,2)\)-survivable network design problem, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, A 3/2-Approximation for the Metric Many-Visits Path TSP, Some Results about the Contractions and the Pendant Pairs of a Submodular System, Robust Monotone Submodular Function Maximization, Quantum machine learning: a classical perspective, Decomposition Algorithm for the Single Machine Scheduling Polytope, Submodular Functions: Learnability, Structure, and Optimization, Unnamed Item, Finding a Stable Allocation in Polymatroid Intersection, Hypergraph Cuts with General Splitting Functions, Algorithms for maximizing monotone submodular function minus modular function under noise, Optimal hierarchical clustering on a graph, ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM, Distributed strategy selection: a submodular set function maximization approach, Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints, The Mixed Evacuation Problem, Unnamed Item, Constraint generation approaches for submodular function maximization leveraging graph properties, On optimization problems in acyclic hypergraphs, Unnamed Item, Unnamed Item, Theory of Principal Partitions Revisited, Graphic Submodular Function Minimization: A Graphic Approach and Applications, The Expressive Power of Valued Constraints: Hierarchies and Collapses, Binarisation for Valued Constraint Satisfaction Problems, The fundamental theorem of linear programming: extensions and applications, Continuous limits of discrete perimeters, Submodular Function Minimization under a Submodular Set Covering Constraint, Unnamed Item, Efficient, optimal stochastic-action selection when limited by an action budget, Discrete convexity and polynomial solvability in minimum 0-extension problems, Computing with Tangles, Geometric Rescaling Algorithms for Submodular Function Minimization, Approximate Modularity Revisited, Finding Submodularity Hidden in Symmetric Difference, Half-integrality, LP-branching, and FPT Algorithms, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Linear Time Algorithms for Happy Vertex Coloring Problems for Trees, Covering Intersecting Bi-set Families under Matroid Constraints, Inferring Relative Ability from Winning Probability in Multientrant Contests, On a General Framework for Network Representability in Discrete Optimization, Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms, Digraphs of Bounded Width, Introduction to the Maximum Solution Problem, The Power of Linear Programming for General-Valued CSPs, Improved Randomized Algorithm for k-Submodular Function Maximization, Tight Approximation for Unconstrained XOS Maximization, A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering