Minimizing symmetric submodular functions
From MaRDI portal
Publication:1290631
DOI10.1007/BF01585863zbMath0949.90076OpenAlexW2043525538MaRDI QIDQ1290631
Publication date: 28 June 1999
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01585863
Related Items
Realizing symmetric set functions as hypergraph cut capacity, On generalized greedy splitting algorithms for multiway partition problems, Maximizing Symmetric Submodular Functions, Some Results about the Contractions and the Pendant Pairs of a Submodular System, Minimum degree orderings, Minimum Cuts and Sparsification in Hypergraphs, Faster connectivity in low-rank hypergraphs via expander decomposition, Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions, Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs, On Submodular Search and Machine Scheduling, Tree-representation of set families and applications to combinatorial decompositions, A note on the minimization of symmetric and general submodular functions, A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint, The Expressive Power of Valued Constraints: Hierarchies and Collapses, Cuts in undirected graphs. II, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, Source location in undirected and directed hypergraphs, Submodular Cost Allocation Problem and Applications, Graph cuts with interacting edge weights: examples, approximations, and algorithms, The expressive power of valued constraints: Hierarchies and collapses, Graph connectivity and its augmentation: Applications of MA orderings, Greedy splitting algorithms for approximating multiway partition problems, Locating tree-shaped facilities using the ordered median objective, Minimizing a sum of submodular functions, A strongly polynomial time algorithm for a constrained submodular optimization problem, A note on submodular function minimization with covering type linear constraints, Exploiting structure of chance constrained programs via submodularity, Submodular function minimization, Unnamed Item, Finding Submodularity Hidden in Symmetric Difference, Symmetric submodular system: contractions and Gomory-Hu tree, Recognizing Cartesian products of matrices and polytopes, Efficient search for informational cores in complex systems: application to brain networks, Unifying the representation of symmetric crossing families and weakly partitive families, A combinatorial algorithm minimizing submodular functions in strongly polynomial time., A fully combinatorial algorithm for submodular function minimization.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Canonical decompositions of symmetric submodular systems
- An efficient algorithm for the minimum capacity cut problem
- Decomposition of submodular functions
- On submodular function minimization
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Submodular functions and optimization
- Maximum concurrent flows and minimum cuts
- Separating from the dominant of the spanning tree polytope
- Geometric algorithms and combinatorial optimization
- Submodular functions and electrical networks
- Implementing an efficient minimum capacity cut algorithm
- Minimizing submodular functions over families of sets
- Submodular systems and related topics
- Optimal attack and reinforcement of a network
- Multi-Terminal Network Flows
- Odd Minimum Cut-Sets and b-Matchings
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Minimizing a Submodular Function on a Lattice
- A simple min-cut algorithm
- On Flows in Pseudosymmetric Networks