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)- 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
- Weakly polynomial-time algorithms to minimize 2/3-submodular functions
- 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
- Linearly representable submodular functions: an algebraic algorithm for minimization
- Theory of principal partitions revisited
- Equivalence of convex minimization problems over base polytopes
- Simple push-relabel algorithms for matroids and submodular flows
- Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function
- Maximization of submodular functions: theory and enumeration algorithms
- Subspace arrangements, graph rigidity and derandomization through submodular optimization
- Separation of partition inequalities with terminals
- A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
- Reachability in arborescence packings
- The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game
- Approximation algorithms for two extensions of min-k-union
- Rank-width: algorithmic and structural results
- An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
- Testing branch-width
- The Alcuin Number of a Graph
- The complexity of soft constraint satisfaction
- Half-integrality, LP-branching, and FPT algorithms
- Matroid coflow scheduling
- Generalized skew bisubmodularity: a characterization and a min-max theorem
- Inferring relative ability from winning probability in multientrant contests
- Effective divisor classes on metric graphs
- Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost
- Quantum machine learning: a classical perspective
- Improved bound for the Carathéodory rank of the bases of a matroid
- On submodular function minimization
- Robust monotone submodular function maximization
- Minimizing symmetric convex functions over hybrid of continuous and discrete convex sets
- Complexity and approximations for submodular minimization problems on two variables per inequality constraints
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- Spanning tree with lower bound on the degrees
- Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
- Submodular functions: from discrete to continuous domains
- Complexity of the cluster deletion problem on subclasses of chordal graphs
- An exact cutting plane method for k-submodular function maximization
- A tight analysis of the submodular-supermodular procedure
- A polynomial algorithm for a class of 0-1 fractional programming problems involving composite functions, with an application to additive clustering
- On optimization problems in acyclic hypergraphs
- Continuous limits of discrete perimeters
- Hypergraph Cuts with General Splitting Functions
- scientific article; zbMATH DE number 2086909 (Why is no real title available?)
- On total variation minimization and surface evolution using parametric maximum flows
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
- Interactive optimization of submodular functions under matroid constraints
- Decomposition algorithm for the single machine scheduling polytope
- Symmetric submodular system: contractions and Gomory-Hu tree
- Supermodular functions and the complexity of MAX CSP
- Efficient minimization of higher order submodular functions using monotonic Boolean functions
- scientific article; zbMATH DE number 7378329 (Why is no real title available?)
- Classes of submodular constraints expressible by graph cuts
- Optimal Boolean lattice-based algorithms for the U-curve optimization problem
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- Minimizing the sum of the \(k\) largest functions in linear time.
- On the complexity of submodular function minimisation on diamonds
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
- Permutatorial optimization via the permutahedron
- Minimization problems with non-submodular cover constraint
- Efficient designs for Bayesian networks with sub-tree bounds
- Optimal allocation of stock levels and stochastic customer demands to a capacitated resource
- Partitioning posets
- Efficient joint object matching via linear programming
- Global approximation of local optimality: nonsubmodular optimization
- A note on the minimization of symmetric and general submodular functions
- Minimization of locally defined submodular functions by optimal soft arc consistency
- Generalized class cover problem with axis-parallel strips
- Isolated scattering number of split graphs and graph products
- Regularized nonmonotone submodular maximization
- Tight approximation for unconstrained XOS maximization
- Decreasing minimization on M-convex sets: algorithms and applications
- Informative path planning as a maximum traveling salesman problem with submodular rewards
- A branch-and-cut algorithm for the multiple Steiner TSP with order constraints
- Supermodularity in unweighted graph optimization. III: Highly connected digraphs
- Approximation algorithms for general one-warehouse multi-retailer systems
- Strongly stable matchings under matroid constraints
- Submodular function minimization and polarity
- scientific article; zbMATH DE number 7255156 (Why is no real title available?)
- Finding diverse minimum s-t cuts
- 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
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)
