A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
From MaRDI portal
Recommendations
- A fully combinatorial algorithm for submodular function minimization.
- A faster strongly polynomial time algorithm for submodular function minimization
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- scientific article; zbMATH DE number 7051294
- scientific article; zbMATH DE number 2119755
- A strongly polynomial time algorithm for a constrained submodular optimization problem
- scientific article; zbMATH DE number 876702
- Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
Cites work
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 1568067 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- A Selection Problem of Shared Fixed Costs and Network Flows
- Computing Maximal “Polymatroidal” Network Flows
- Finding feasible vectors of Edmonds-Giles polyhedra
- Geometric algorithms and combinatorial optimization
- Maximal Closure of a Graph and Applications to Combinatorial Problems
- Minimizing symmetric submodular functions
- On submodular function minimization
- Submodular functions and optimization
- Testing membership in matroid polyhedra
- The Partial Order of a Polymatroid Extreme Point
- The ellipsoid method and its consequences in combinatorial optimization
Cited in
(only showing first 100 items - show all)- Informative path planning as a maximum traveling salesman problem with submodular rewards
- Supermodularity in unweighted graph optimization. III: Highly connected digraphs
- Approximation algorithms for general one-warehouse multi-retailer systems
- Submodular function minimization and polarity
- scientific article; zbMATH DE number 7255156 (Why is no real title available?)
- Covering intersecting bi-set families under matroid constraints
- Build-pack planning for hard disk drive assembly with approved vendor matrices and stochastic demands
- Stochastic block-coordinate gradient projection algorithms for submodular maximization
- The expressive power of valued constraints: Hierarchies and collapses
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Separation of partition inequalities for the \((1,2)\)-survivable network design problem
- Discrete Newton methods for the evacuation problem
- A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions
- Submodular function minimization
- Efficient, optimal stochastic-action selection when limited by an action budget
- ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
- Approximability of clausal constraints
- Algebraic and topological closure conditions for classes of pseudo-Boolean functions
- Global optimization for first order Markov random fields with submodular priors
- Minimizing convex functions with rational minimizers
- Discrete convexity and polynomial solvability in minimum 0-extension problems
- scientific article; zbMATH DE number 7051294 (Why is no real title available?)
- Dijkstra's algorithm and L-concave function maximization
- Multi-agent submodular optimization
- A descent method for submodular function minimization
- The fundamental theorem of linear programming: extensions and applications
- A fully combinatorial algorithm for submodular function minimization.
- Pseudo-Boolean optimization
- Approximate modularity revisited
- Semiconductor lot allocation using robust optimization
- Is submodularity testable?
- Minimum degree orderings
- The power of linear programming for general-valued CSPs
- Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
- Realizing symmetric set functions as hypergraph cut capacity
- Designing two-echelon supply networks
- Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
- The warehouse-retailer network design game
- Maximizing a non-decreasing non-submodular function subject to various types of constraints
- A note on submodular function minimization by Chubanov's LP algorithm
- A scaling algorithm for optimizing arbitrary functions over vertices of polytopes
- Submodular functions: learnability, structure, and optimization
- Constraint generation approaches for submodular function maximization leveraging graph properties
- Introduction to the Maximum Solution Problem
- Minimizing submodular functions on diamonds via generalized fractional matroid matchings
- Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
- On a general framework for network representability in discrete optimization
- The mixed evacuation problem
- scientific article; zbMATH DE number 3847217 (Why is no real title available?)
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- The mixed evacuation problem
- Graphic submodular function minimization: a graphic approach and applications
- Robust monotone submodular function maximization
- The \(b\)-branching problem in digraphs
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- A note on Schrijver's submodular function minimization algorithm.
- A note on submodular function minimization with covering type linear constraints
- scientific article; zbMATH DE number 910864 (Why is no real title available?)
- Computing with tangles
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
- On a general framework for network representability in discrete optimization (extended abstract)
- Traveling salesman games with the Monge property
- Vulnerability parameters of split graphs
- The median partition and submodularity
- Distributed strategy selection: a submodular set function maximization approach
- A faster strongly polynomial time algorithm for submodular function minimization
- The expressive power of binary submodular functions
- Improved randomized algorithm for \(k\)-submodular function maximization
- Differential approximation schemes for half-product related functions and their scheduling applications
- A variation of DS decomposition in set function optimization
- Finding a stable allocation in polymatroid intersection
- Polynomial combinatorial algorithms for skew-bisubmodular function minimization
- ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
- Matroid optimisation problems with nested non-linear monomials in the objective function
- Finding submodularity hidden in symmetric difference
- Submodular functions and valued constraint satisfaction problems over infinite domains
- A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
- Computing an element in the lexicographic kernel of a game
- Submodular function minimization under a submodular set covering constraint
- Preference swaps for the stable matching problem
- Set function optimization
- A strongly polynomial time algorithm for a constrained submodular optimization problem
- Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- A strongly polynomial algorithm for line search in submodular polyhedra
- Biased positional games on matroids
- Coordinatewise domain scaling algorithm for M-convex function minimization
- A capacity scaling algorithm for M-convex submodular flow
- Matroid optimization problems with monotone monomials in the objective
- Geometric rescaling algorithms for submodular function minimization
- The b‐bibranching problem: TDI system, packing, and discrete convexity
- Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
- Binarisation for valued constraint satisfaction problems
- Computational geometric approach to submodular function minimization for multiclass queueing systems
- Eisenberg-Gale markets: algorithms and game-theoretic properties
- Some results about the contractions and the pendant pairs of a submodular system
- On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty
- Theory of principal partitions revisited
- Equivalence of convex minimization problems over base polytopes
This page was built for publication: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850505)
