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
- 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
- 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?)
- 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 ellipsoid method and its consequences in combinatorial optimization
- The Partial Order of a Polymatroid Extreme Point
Cited in
(only showing first 100 items - show all)- A faster strongly polynomial time algorithm for submodular function minimization
- Minimization of locally defined submodular functions by optimal soft arc consistency
- Maximization of submodular functions: theory and enumeration algorithms
- On submodular function minimization
- Improved bound for the Carathéodory rank of the bases of a matroid
- A note on Schrijver's submodular function minimization algorithm.
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- A note on the minimization of symmetric and general submodular functions
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- A descent method for submodular function minimization
- On a general framework for network representability in discrete optimization
- The mixed evacuation problem
- Matroid optimisation problems with nested non-linear monomials in the objective function
- Stochastic block-coordinate gradient projection algorithms for submodular maximization
- Spanning tree with lower bound on the degrees
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
- Biased positional games on matroids
- Coordinatewise domain scaling algorithm for M-convex function minimization
- A capacity scaling algorithm for M-convex submodular flow
- Polynomial combinatorial algorithms for skew-bisubmodular function minimization
- Robust monotone submodular function maximization
- Complexity and approximations for submodular minimization problems on two variables per inequality constraints
- Traveling salesman games with the Monge property
- A fully combinatorial algorithm for submodular function minimization.
- Minimizing the sum of the \(k\) largest functions in linear time.
- Separation of partition inequalities for the \((1,2)\)-survivable network design problem
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- Simple push-relabel algorithms for matroids and submodular flows
- Computational geometric approach to submodular function minimization for multiclass queueing systems
- Equivalence of convex minimization problems over base polytopes
- A note on submodular function minimization by Chubanov's LP algorithm
- Matroid optimization problems with monotone monomials in the objective
- An exact cutting plane method for k-submodular function maximization
- Permutatorial optimization via the permutahedron
- Decreasing minimization on M-convex sets: algorithms and applications
- Submodular function minimization and polarity
- A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
- Maximizing a non-decreasing non-submodular function subject to various types of constraints
- A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
- Reachability in arborescence packings
- Minimizing submodular functions on diamonds via generalized fractional matroid matchings
- Effective divisor classes on metric graphs
- Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost
- A variation of DS decomposition in set function optimization
- The \(b\)-branching problem in digraphs
- Optimal Boolean lattice-based algorithms for the U-curve optimization problem
- A scaling algorithm for optimizing arbitrary functions over vertices of polytopes
- The median partition and submodularity
- Dijkstra's algorithm and L-concave function maximization
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
- Symmetric submodular system: contractions and Gomory-Hu tree
- Set function optimization
- Discrete Newton methods for the evacuation problem
- Generalized skew bisubmodularity: a characterization and a min-max theorem
- Informative path planning as a maximum traveling salesman problem with submodular rewards
- A tight analysis of the submodular-supermodular procedure
- Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
- Separation of partition inequalities with terminals
- Supermodular functions and the complexity of MAX CSP
- Optimal allocation of stock levels and stochastic customer demands to a capacitated resource
- Rank-width: algorithmic and structural results
- Submodular functions: from discrete to continuous domains
- A strongly polynomial algorithm for line search in submodular polyhedra
- Build-pack planning for hard disk drive assembly with approved vendor matrices and stochastic demands
- The complexity of soft constraint satisfaction
- Computing an element in the lexicographic kernel of a game
- The warehouse-retailer network design game
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function
- On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty
- Interactive optimization of submodular functions under matroid constraints
- Preference swaps for the stable matching problem
- Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
- Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines
- Half-integrality, LP-branching, and FPT algorithms
- Covering intersecting bi-set families under matroid constraints
- On a general framework for network representability in discrete optimization (extended abstract)
- Realizing symmetric set functions as hypergraph cut capacity
- The mixed evacuation problem
- Theory of principal partitions revisited
- Graphic submodular function minimization: a graphic approach and applications
- The fundamental theorem of linear programming: extensions and applications
- Submodular function minimization under a submodular set covering constraint
- Robust monotone submodular function maximization
- Decomposition algorithm for the single machine scheduling polytope
- Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
- Subspace arrangements, graph rigidity and derandomization through submodular optimization
- scientific article; zbMATH DE number 3847217 (Why is no real title available?)
- ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
- The Alcuin Number of a Graph
- Continuous limits of discrete perimeters
- ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
- scientific article; zbMATH DE number 569962 (Why is no real title available?)
- Quantum machine learning: a classical perspective
- Submodular functions: learnability, structure, and optimization
- scientific article; zbMATH DE number 7051294 (Why is no real title available?)
- Is submodularity testable?
- scientific article; zbMATH DE number 2086909 (Why is no real title available?)
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)
