Minimizing submodular functions over families of sets
From MaRDI portal
Publication:1906848
DOI10.1007/BF01192523zbMath0840.90109OpenAlexW2050977796MaRDI QIDQ1906848
Michel X. Goemans, V. S. Ramakrishnan
Publication date: 24 January 1996
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01192523
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Connectivity (05C40)
Related Items (15)
Supermodular functions and the complexity of MAX CSP ⋮ Reachability in arborescence packings ⋮ Co-density and fractional edge cover packing ⋮ Advances on strictly \(\varDelta \)-modular IPs ⋮ Unnamed Item ⋮ Densities, Matchings, and Fractional Edge-Colorings ⋮ Computational complexity analysis of the sensor location flow observability problem ⋮ An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations ⋮ The separation problem of rounded capacity inequalities: some polynomial cases ⋮ Ideal clutters ⋮ Edge-connectivity augmentation of graphs over symmetric parity families ⋮ A new contraction technique with applications to congruency-constrained cuts ⋮ Symmetric submodular system: contractions and Gomory-Hu tree ⋮ Minimizing symmetric submodular functions ⋮ A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering
Cites Work
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- A construction for binary matroids
- The ellipsoid method and its consequences in combinatorial optimization
- Submodular functions and optimization
- A primal-dual approximation algorithm for generalized Steiner network problems
- Multi-Terminal Network Flows
- Odd Minimum Cut-Sets and b-Matchings
- A General Approximation Technique for Constrained Forest Problems
- Unnamed Item
This page was built for publication: Minimizing submodular functions over families of sets
