A push-relabel framework for submodular function minimization and applications to parametric optimization

DOI10.1016/S0166-218X(02)00458-4zbMath1030.90097MaRDI QIDQ1410685

Satoru Iwata, Lisa K. Fleischer

Publication date: 14 October 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Submodular functionrunning timeParametric optimizationSchrijver's algorithmstrong map sequence

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Sensitivity, stability, parametric optimization (90C31) Combinatorial optimization (90C27)

Related Items

Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, A cross-monotonic cost-sharing scheme for the concave facility location game, Improved Markov chain Monte Carlo method for cryptanalysis substitution-transposition cipher, Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties, Simple push-relabel algorithms for matroids and submodular flows, Equivalence of convex minimization problems over base polytopes, Approximation algorithms for the minimum power cover problem with submodular/linear penalties, Hypergraphic submodular function minimization, An approximation algorithm for the dynamic facility location problem with submodular penalties, A strongly polynomial algorithm for line search in submodular polyhedra, On-line single machine scheduling with release dates and submodular rejection penalties, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Theory of Principal Partitions Revisited, Unnamed Item, Approximation algorithms for the dynamic \(k\)-level facility location problems, LP-based covering games with low price of anarchy, Efficient minimization of higher order submodular functions using monotonic Boolean functions, Structural and algorithmic properties for parametric minimum cuts, Approximation algorithms for the submodular edge cover problem with submodular penalties, Submodular function minimization, The warehouse-retailer network design game, Approximation algorithm for stochastic set cover problem, Approximation algorithms for the multiprocessor scheduling with submodular penalties, A primal-dual algorithm for the minimum partial set multi-cover problem, A primal-dual -approximation algorithm for the stochastic facility location problem with submodular penalties, Discrete Newton methods for the evacuation problem, Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties

Cites Work

• Unnamed Item
• Unnamed Item
• Testing membership in matroid polyhedra
• On submodular function minimization
• The ellipsoid method and its consequences in combinatorial optimization
• New algorithms for the intersection problem of submodular systems
• Geometric algorithms and combinatorial optimization
• A capacity scaling algorithm for convex cost submodular flows
• A faster capacity scaling algorithm for minimum cost submodular flow
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Layered Augmenting Path Algorithms
• A new approach to the maximum-flow problem
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Optimal flows in networks with multiple sources and sinks
• Minimizing a Submodular Function on a Lattice
• A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
• A Fast Parametric Maximum Flow Algorithm and Applications
• On Nonlinear Fractional Programming