Graph cuts with interacting edge weights: examples, approximations, and algorithms
From MaRDI portal
Publication:517305
DOI10.1007/s10107-016-1038-yzbMath1362.68231arXiv1402.0240OpenAlexW2963220807MaRDI QIDQ517305
Jeff A. Bilmes, Stefanie Jegelka
Publication date: 23 March 2017
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.0240
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ The label cut problem with respect to path length and label frequency ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ A note on submodular function minimization with covering type linear constraints ⋮ A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
Uses Software
Cites Work
- Nonlinear total variation based noise removal algorithms
- An FPTAS for optimizing a class of low-rank functions over a polytope
- Efficient minimization of higher order submodular functions using monotonic Boolean functions
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- Approximation and hardness results for label cut and related problems
- Minimizing a sum of submodular functions
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- On total variation minimization and surface evolution using parametric maximum flows
- The expressive power of binary submodular functions
- Minimum cut bases in undirected networks
- Decomposition of submodular functions
- Some simplified NP-complete graph problems
- Minimizing symmetric submodular functions
- Submodular functions and electrical networks
- An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set
- Approximation algorithms and hardness results for labeled connectivity problems
- Multicommodity flows and cuts in polymatroidal networks
- Symmetry and Approximability of Submodular Maximization Problems
- Combinatorial Continuous Maximum Flow
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- Maximal Flow Through a Network
- Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
- Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- Layered Augmenting Path Algorithms
- Minimum cost flow with set-constraints
- Computing Maximal “Polymatroidal” Network Flows
- Submodular Functions: Learnability, Structure, and Optimization
- Submodular Function Minimization under Covering Constraints
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- Exact Algorithms for Combinatorial Optimization Problems with Submodular Objective Functions
- Probability and Computing
- Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Graph cuts with interacting edge weights: examples, approximations, and algorithms
