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 (only showing first 100 items - show all)

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

This page was built for publication: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions