A combinatorial algorithm minimizing submodular functions in strongly polynomial time.

DOI10.1006/JCTB.2000.1989zbMath1052.90067OpenAlexW2035575256WikidataQ62111283 ScholiaQ62111283MaRDI QIDQ1850505

No author found.

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (only showing first 100 items - show all)

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

Cites Work

This page was built for publication: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.