A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
From MaRDI portal
Publication:1850505
DOI10.1006/jctb.2000.1989zbMath1052.90067OpenAlexW2035575256WikidataQ62111283 ScholiaQ62111283MaRDI QIDQ1850505
Publication date: 10 December 2002
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/2108
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items
A 3/2-Approximation for the Metric Many-Visits Path TSP, Some Results about the Contractions and the Pendant Pairs of a Submodular System, Approximation algorithms for general one-warehouse multi-retailer systems, Robust Monotone Submodular Function Maximization, Quantum machine learning: a classical perspective, Decomposition Algorithm for the Single Machine Scheduling Polytope, Submodular Functions: Learnability, Structure, and Optimization, Unnamed Item, Finding a Stable Allocation in Polymatroid Intersection, Hypergraph Cuts with General Splitting Functions, Efficient joint object matching via linear programming, The b‐bibranching problem: TDI system, packing, and discrete convexity, ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM, Distributed strategy selection: a submodular set function maximization approach, The Mixed Evacuation Problem, Constraint generation approaches for submodular function maximization leveraging graph properties, On optimization problems in acyclic hypergraphs, Unnamed Item, Unnamed Item, Theory of Principal Partitions Revisited, Graphic Submodular Function Minimization: A Graphic Approach and Applications, ISOLATED SCATTERING NUMBER OF SPLIT GRAPHS AND GRAPH PRODUCTS, Binarisation for Valued Constraint Satisfaction Problems, Submodularity in Conic Quadratic Mixed 0–1 Optimization, The Alcuin Number of a Graph, Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization, The fundamental theorem of linear programming: extensions and applications, Continuous limits of discrete perimeters, Submodular Function Minimization under a Submodular Set Covering Constraint, Unnamed Item, Vulnerability parameters of split graphs, Unnamed Item, Efficient, optimal stochastic-action selection when limited by an action budget, Discrete convexity and polynomial solvability in minimum 0-extension problems, Computing with Tangles, Geometric Rescaling Algorithms for Submodular Function Minimization, Approximate Modularity Revisited, Finding Submodularity Hidden in Symmetric Difference, Half-integrality, LP-branching, and FPT Algorithms, Supermodularity in Unweighted Graph Optimization III: Highly Connected Digraphs, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Covering Intersecting Bi-set Families under Matroid Constraints, Inferring Relative Ability from Winning Probability in Multientrant Contests, On a General Framework for Network Representability in Discrete Optimization, Introduction to the Maximum Solution Problem, The Power of Linear Programming for General-Valued CSPs, Improved Randomized Algorithm for k-Submodular Function Maximization, Unnamed Item, Tight Approximation for Unconstrained XOS Maximization, A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering, Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, Realizing symmetric set functions as hypergraph cut capacity, On a general framework for network representability in discrete optimization, The mixed evacuation problem, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, A new greedy strategy for maximizing monotone submodular function under a cardinality constraint, On total variation minimization and surface evolution using parametric maximum flows, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Minimum degree orderings, Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope, Matroid optimisation problems with nested non-linear monomials in the objective function, Separation of partition inequalities with terminals, Supermodular functions and the complexity of MAX CSP, Maximizing a non-decreasing non-submodular function subject to various types of constraints, Designing two-echelon supply networks, An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks, Optimal allocation of stock levels and stochastic customer demands to a capacitated resource, 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, Rank-width: algorithmic and structural results, Effective divisor classes on metric graphs, Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function, Testing branch-width, Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost, On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty, Classes of submodular constraints expressible by graph cuts, 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, Submodular functions: from discrete to continuous domains, A variation of DS decomposition in set function optimization, The \(b\)-branching problem in digraphs, Improved bound for the Carathéodory rank of the bases of a matroid, A note on Schrijver's submodular function minimization algorithm., A strongly polynomial algorithm for line search in submodular polyhedra, Optimal Boolean lattice-based algorithms for the U-curve optimization problem, A push-relabel framework for submodular function minimization and applications to parametric optimization, A note on the minimization of symmetric and general submodular functions, Build-pack planning for hard disk drive assembly with approved vendor matrices and stochastic demands, Interactive optimization of submodular functions under matroid constraints, Preference swaps for the stable matching problem, Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem., Stochastic block-coordinate gradient projection algorithms for submodular maximization, Is submodularity testable?, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, The complexity of soft constraint satisfaction, On the complexity of submodular function minimisation on diamonds, Complexity of the cluster deletion problem on subclasses of chordal graphs, Partitioning posets, Spanning tree with lower bound on the degrees, Efficient minimization of higher order submodular functions using monotonic Boolean functions, The median partition and submodularity, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Efficient designs for Bayesian networks with sub-tree bounds, Computing an element in the lexicographic kernel of a game, Dijkstra's algorithm and L-concave function maximization, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches, The expressive power of valued constraints: Hierarchies and collapses, Algebraic and topological closure conditions for classes of pseudo-Boolean functions, The expressive power of binary submodular functions, Global optimization for first order Markov random fields with submodular priors, Pseudo-Boolean optimization, Approximability of clausal constraints, Biased positional games on matroids, A note on submodular function minimization by Chubanov's LP algorithm, A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions, Semiconductor lot allocation using robust optimization, 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, A note on submodular function minimization with covering type linear constraints, Eisenberg-Gale markets: algorithms and game-theoretic properties, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, Submodular function minimization, Differential approximation schemes for half-product related functions and their scheduling applications, The warehouse-retailer network design game, Robust monotone submodular function maximization, Complexity and approximations for submodular minimization problems on two variables per inequality constraints, Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines, Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times, A faster strongly polynomial time algorithm for submodular function minimization, Symmetric submodular system: contractions and Gomory-Hu tree, Minimization of locally defined submodular functions by optimal soft arc consistency, Matroid optimization problems with monotone monomials in the objective, Maximization of submodular functions: theory and enumeration algorithms, Set function optimization, An exact cutting plane method for \(k\)-submodular function maximization, Traveling salesman games with the Monge property, Permutatorial optimization via the permutahedron, Discrete Newton methods for the evacuation problem, Decreasing minimization on M-convex sets: algorithms and applications, A fully combinatorial algorithm for submodular function minimization., Generalized skew bisubmodularity: a characterization and a min-max theorem, Submodular function minimization and polarity, Informative path planning as a maximum traveling salesman problem with submodular rewards, A tight analysis of the submodular-supermodular procedure, Separation of partition inequalities for the \((1,2)\)-survivable network design problem, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding feasible vectors of Edmonds-Giles polyhedra
- Testing membership in matroid polyhedra
- On submodular function minimization
- The ellipsoid method and its consequences in combinatorial optimization
- Submodular functions and optimization
- Geometric algorithms and combinatorial optimization
- Minimizing symmetric submodular functions
- The Partial Order of a Polymatroid Extreme Point
- Computing Maximal “Polymatroidal” Network Flows
- Maximal Closure of a Graph and Applications to Combinatorial Problems
- A Selection Problem of Shared Fixed Costs and Network Flows
