Directed submodularity, ditroids and directed submodular flows
From MaRDI portal
Publication:1116891
DOI10.1007/BF01589420zbMath0665.90075OpenAlexW2022245976MaRDI QIDQ1116891
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/bf01589420
matroidssubmodular functionsTotal dual integralitydirected subsetsditroidspolymatroidal network flows
Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items (24)
Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization ⋮ Circuit separation for symmetric matroids ⋮ A characterization of bisubmodular functions ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ A polyhedral approach to bisubmodular function minimization ⋮ The delta-sum of matching delta-matroids ⋮ Coverings and delta-coverings ⋮ From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals ⋮ Recent progress on integrally convex functions ⋮ Generalized roof duality and bisubmodular functions ⋮ Characterizations of the set of integer points in an integral bisubmodular polyhedron ⋮ Bipolarization of posets and natural interpolation ⋮ The Orthant Non-Interaction Theorem for Certain Combinatorial Polyhedra and its Implications in the Intersection and the Dilworth Truncation of Bisubmodular Functions ⋮ Representability of \(\bigtriangleup\)-matroids over \(GF(2)\) ⋮ \(b\)-matching degree-sequence polyhedra ⋮ L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem ⋮ Polynomial combinatorial algorithms for skew-bisubmodular function minimization ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ On structures of bisubmodular polyhedra ⋮ An exact cutting plane method for \(k\)-submodular function maximization ⋮ Signed ring families and signed posets ⋮ Generalized skew bisubmodularity: a characterization and a min-max theorem ⋮ Bisubmodular polyhedra, simplicial divisions, and discrete convexity ⋮ Parametric bisubmodular function minimization and its associated signed ring family
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
- Canonical decompositions of symmetric submodular systems
- A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors
- Finding feasible vectors of Edmonds-Giles polyhedra
- Convexity in oriented matroids
- Decomposition of regular matroids
- Minimization on submodular flows
- Orientability of matroids
- A combinatorial abstraction of linear programming
- A submodular network simplex method
- Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
- On the subdifferential of a submodular function
- Structures of polyhedra determined by submodular functions on crossing families
- A Primal-Dual Algorithm for Submodular Flows
- On box totally dual integral polyhedra
- Submodular systems and related topics
- Odd Submodular Functions, Dilworth Functions and Discrete Convex Functions
- Minimum cost flow with set-constraints
- Minimization of Some Nonlinear Functions over Polymatroidal Network Flows
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Computing Maximal “Polymatroidal” Network Flows
- An analysis of approximations for maximizing submodular set functions—I
- An Algorithm for Submodular Functions on Graphs
- Flow Network Formulations of Polymatroid Optimization Problems
This page was built for publication: Directed submodularity, ditroids and directed submodular flows
