Generalized polymatroids and submodular flows

DOI10.1007/BF01589418zbMath0665.90073OpenAlexW2042275390WikidataQ56987199 ScholiaQ56987199MaRDI QIDQ1116889

András Frank, Éva Tardos

Publication date: 1988

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01589418

zbMATH Keywords

truncationgreedy algorithmmatroidssupermodular functionsfacetstotal dual integralityPolyhedrabi-truncationgeneralized polymatroidssubmodular flow systems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Polytopes and polyhedra (52Bxx)

Related Items

Submodularity and its application to some global constraints, A fast cost scaling algorithm for submodular flow, On box totally dual integral polyhedra, A 3/2-Approximation for the Metric Many-Visits Path TSP, Algorithms for finding a rooted \((k,1)\)-edge-connected orientation, A capacity scaling algorithm for convex cost submodular flows, The membership problem in jump systems, Optimization over the polyhedron determined by a submodular function on a co-intersecting family, An application of submodular flows, Submodular linear programs on forests, Pre-emptive scheduling problems with controllable processing times, Simple push-relabel algorithms for matroids and submodular flows, Matroid rank functions and discrete concavity, Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds, Characterizing and recognizing generalized polymatroids, A generalized-polymatroid approach to disjoint common independent sets in two matroids, Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle, Gross substitution, discrete convexity, and submodularity, Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability, New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities., A Survey on Covering Supermodular Functions, Graphic Submodular Function Minimization: A Graphic Approach and Applications, Edge splitting and connectivity augmentation in directed hypergraphs., A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas, Tree-compositions and orientations, Preemptive scheduling on uniform parallel machines with controllable job processing times, Solution concepts for games with general coalitional structure, Application of M-convex submodular flow problem to mathematical economics, Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization, A dual algorithm for submodular flow problems, A note on the Frank-Tardos bi-truncation algorithm for crossing- submodular functions, A framework of discrete DC programming by discrete convex analysis, Compression of \(\mathrm{M}^\natural\)-convex functions -- flag matroids and valuated permutohedra, Simpler exchange axioms for M-concave functions on generalized polymatroids, Optimal Matching Forests and Valuated Delta-Matroids, Two-machine open shop problem with controllable processing times, Envy-free matchings with lower quotas, A cost-scaling algorithm for \(0-1\) submodular flows, Submodular functions in graph theory, Discrete convexity and unimodularity. I., Budgeted matching and budgeted matroid intersection via the gasoline puzzle, Discrete convexity and equilibria in economies with indivisible goods and money, Coordinatewise domain scaling algorithm for M-convex function minimization, Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella., Flip distances between graph orientations, Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings, SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Unnamed Item, Covering skew-supermodular functions by hypergraphs of minimum total size, Base polytopes of series-parallel posets: Linear description and optimization, The nucleon of cooperative games and an algorithm for matching games, Discrete convex analysis, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, Extension of M-convexity and L-convexity to polyhedral convex functions, Polyhedral structure of submodular and posi-modular systems, Decreasing minimization on M-convex sets: algorithms and applications, A fully combinatorial algorithm for submodular function minimization., Some recent results in the analysis of greedy algorithms for assignment problems, Note on the polyhedral description of the Minkowski sum of two L-convex sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Packing and covering of crossing families of cuts
• A note on Frank's generalized polymatroids
• On the number of common bases of two matroids
• Finding feasible vectors of Edmonds-Giles polyhedra
• On submodular function minimization
• An application of submodular flows
• On the orientation of graphs
• On total dual integrality
• How to make a digraph strongly connected
• On matroid intersections
• Minimization on submodular flows
• The ellipsoid method and its consequences in combinatorial optimization
• An unbounded matroid intersection polyhedron
• Covering the edge set of a directed graph with trees
• Blocking, antiblocking, and pairs of matroids and polymatroids
• Cores of convex games
• NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
• The perfectly matchable subgraph polytope of a bipartite graph
• Matroid Intersection
• Covering directed and odd cuts
• Note on Independence Functions
• On the Problem of Decomposing a Graph into n Connected Factors
• Proving total dual integrality with cross-free families—A general framework
• A NOTE ON SUBMODULAR FUNCTIONS ON DISTRIBUTIVE LATTICES
• A CHARACTERIZATION OF FACES OF THE BASE POLYHEDRON ASSOCIATED WITH A SUBMODULAR SYSTEM
• Adjacency on polymatroids
• Structures of polyhedra determined by submodular functions on crossing families
• A Primal-Dual Algorithm for Submodular Flows
• The Partial Order of a Polymatroid Extreme Point
• On box totally dual integral polyhedra
• Layered Augmenting Path Algorithms
• Submodular systems and related topics
• Optimal attack and reinforcement of a network
• Connected and alternating vectors: Polyhedra and algorithms
• Minimum cost flow with set-constraints
• A weighted matroid intersection algorithm
• On Generic Rigidity in the Plane
• Computing Maximal “Polymatroidal” Network Flows
• A Minimax Equality Related to the Longest Directed Path in an Acyclic Graph
• Matroid intersection algorithms
• Facets of the knapsack polytope
• Rado's theorem for polymatroids
• MATROIDS AND SUBMODULAR FUNCTIONS
• A generalization of max flow—min cut
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• A Minimax Theorem for Directed Graphs
• An Algorithm for Submodular Functions on Graphs
• Strong maps of geometries
• Minimum partition of a matroid into independent subsets
• Lehmans switching game and a theorem of Tutte and Nash-Williams
• Optimal assignments in an ordered set: An application of matroid theory
• A generalization of Kónig's theorem
• Matroids and the greedy algorithm
• Independence Structures and Submodular Functions
• A THEOREM ON INDEPENDENCE RELATIONS