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)- On a general framework for network representability in discrete optimization (extended abstract)
- Robust monotone submodular function maximization
- Hypergraph Cuts with General Splitting Functions
- Equivalence of convex minimization problems over base polytopes
- Simple push-relabel algorithms for matroids and submodular flows
- Rank-width: algorithmic and structural results
- A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
- Computational geometric approach to submodular function minimization for multiclass queueing systems
- On optimization problems in acyclic hypergraphs
- A note on submodular function minimization by Chubanov's LP algorithm
- Coordinatewise domain scaling algorithm for M-convex function minimization
- The warehouse-retailer network design game
- A capacity scaling algorithm for M-convex submodular flow
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
- Discrete convexity and polynomial solvability in minimum 0-extension problems
- Complexity and approximations for submodular minimization problems on two variables per inequality constraints
- Quantum machine learning: a classical perspective
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- On a general framework for network representability in discrete optimization
- The mixed evacuation problem
- Permutatorial optimization via the permutahedron
- Separation of partition inequalities for the \((1,2)\)-survivable network design problem
- The mixed evacuation problem
- Subspace arrangements, graph rigidity and derandomization through submodular optimization
- A strongly polynomial time algorithm for a constrained submodular optimization problem
- The fundamental theorem of linear programming: extensions and applications
- Stochastic block-coordinate gradient projection algorithms for submodular maximization
- Preference swaps for the stable matching problem
- Optimal Boolean lattice-based algorithms for the U-curve optimization problem
- Generalized skew bisubmodularity: a characterization and a min-max theorem
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- Improved randomized algorithm for \(k\)-submodular function maximization
- Semiconductor lot allocation using robust optimization
- The Alcuin Number of a Graph
- A descent method for submodular function minimization
- Decreasing minimization on M-convex sets: algorithms and applications
- Matroid optimization problems with monotone monomials in the objective
- Informative path planning as a maximum traveling salesman problem with submodular rewards
- A tight analysis of the submodular-supermodular procedure
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Submodular functions: from discrete to continuous domains
- Theory of principal partitions revisited
- Multi-agent submodular optimization
- An exact cutting plane method for \(k\)-submodular function maximization
- Submodular function minimization and polarity
- Approximation algorithms for general one-warehouse multi-retailer systems
- Spanning tree with lower bound on the degrees
- Binarisation for valued constraint satisfaction problems
- Matroid optimisation problems with nested non-linear monomials in the objective function
- Covering intersecting bi-set families under matroid constraints
- Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines
- Maximizing a non-decreasing non-submodular function subject to various types of constraints
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
- Submodular function minimization under a submodular set covering constraint
- Pseudo-Boolean optimization
- Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
- Complexity of the cluster deletion problem on subclasses of chordal graphs
- On submodular function minimization
- scientific article; zbMATH DE number 7378329 (Why is no real title available?)
- A faster strongly polynomial time algorithm for submodular function minimization
- scientific article; zbMATH DE number 910864 (Why is no real title available?)
- Dijkstra's algorithm and L-concave function maximization
- Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
- The power of linear programming for general-valued CSPs
- Supermodular functions and the complexity of MAX CSP
- Designing two-echelon supply networks
- The expressive power of binary submodular functions
- Minimization of locally defined submodular functions by optimal soft arc consistency
- Realizing symmetric set functions as hypergraph cut capacity
- Traveling salesman games with the Monge property
- The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game
- On total variation minimization and surface evolution using parametric maximum flows
- Optimal allocation of stock levels and stochastic customer demands to a capacitated resource
- Eisenberg-Gale markets: algorithms and game-theoretic properties
- Graphic submodular function minimization: a graphic approach and applications
- A note on Schrijver's submodular function minimization algorithm.
- Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
- ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
- Classes of submodular constraints expressible by graph cuts
- Approximate modularity revisited
- Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
- A variation of DS decomposition in set function optimization
- On the complexity of submodular function minimisation on diamonds
- scientific article; zbMATH DE number 2086909 (Why is no real title available?)
- ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
- Maximization of submodular functions: theory and enumeration algorithms
- Robust monotone submodular function maximization
- Approximability of clausal constraints
- scientific article; zbMATH DE number 7051294 (Why is no real title available?)
- Is submodularity testable?
- An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
- Differential approximation schemes for half-product related functions and their scheduling applications
- Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
- A fully combinatorial algorithm for submodular function minimization.
- A strongly polynomial algorithm for line search in submodular polyhedra
- Set function optimization
- A note on submodular function minimization with covering type linear constraints
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)
