A faster strongly polynomial time algorithm for submodular function minimization
From MaRDI portal
Publication:1016120
DOI10.1007/s10107-007-0189-2zbMath1179.90290OpenAlexW2050511894WikidataQ59592328 ScholiaQ59592328MaRDI QIDQ1016120
Publication date: 4 May 2009
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-007-0189-2
Related Items
Realizing symmetric set functions as hypergraph cut capacity, The submodular joint replenishment problem, Some Results about the Contractions and the Pendant Pairs of a Submodular System, The Expressive Power of Binary Submodular Functions, Structured Sparsity: Discrete and Convex Approaches, Strong formulations for quadratic optimization with M-matrices and indicator variables, Quantum machine learning: a classical perspective, Intersection Disjunctions for Reverse Convex Sets, Minimizing submodular functions on diamonds via generalized fractional matroid matchings, Rank-width: algorithmic and structural results, Efficient Solution Methods for a General r-Interdiction Median Problem with Fortification, Finding a Stable Allocation in Polymatroid Intersection, Classes of submodular constraints expressible by graph cuts, 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, Hypergraph Cuts with General Splitting Functions, Submodular functions: from discrete to continuous domains, Submodular reassignment problem for reallocating agents to tasks with synergy effects, A variation of DS decomposition in set function optimization, Optimal hierarchical clustering on a graph, Lexicographically optimal earliest arrival flows, Tractability of explaining classifier decisions, Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints, Supermodularity and valid inequalities for quadratic optimization with indicators, Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost, Submodularity in Conic Quadratic Mixed 0–1 Optimization, Stochastic block-coordinate gradient projection algorithms for submodular maximization, Faster algorithms for security games on matroids, A framework of discrete DC programming by discrete convex analysis, Submodular Function Minimization under a Submodular Set Covering Constraint, Efficient minimization of higher order submodular functions using monotonic Boolean functions, The median partition and submodularity, The expressive power of valued constraints: Hierarchies and collapses, A computational study for common network design in multi-commodity supply chains, The expressive power of binary submodular functions, Soft arc consistency revisited, Minimizing a sum of submodular functions, Geometric Rescaling Algorithms for Submodular Function Minimization, Complexity and approximations for submodular minimization problems on two variables per inequality constraints, Symmetric submodular system: contractions and Gomory-Hu tree, Envy-free matchings with one-sided preferences and matroid constraints, Set function optimization, An exact cutting plane method for \(k\)-submodular function maximization, New algorithms for convex cost tension problem with application to computer vision, Discrete Newton methods for the evacuation problem, A Note on Appointment Scheduling with Piecewise Linear Cost Functions, Strongly polynomial FPTASes for monotone dynamic programs, Decreasing minimization on M-convex sets: algorithms and applications, Submodular function minimization and polarity, A game theoretic approach to a problem in polymatroid maximization, A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Submodular function minimization
- On submodular function minimization
- Geometric algorithms and combinatorial optimization
- A note on Schrijver's submodular function minimization algorithm.
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Cores of convex games
- Submodular functions and optimization.
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Improved algorithms for submodular function minimization and submodular flow
- A Faster Scaling Algorithm for Minimizing Submodular Functions
