Discrete convexity and polynomial solvability in minimum 0-extension problems
From MaRDI portal
Publication:5962712
DOI10.1007/s10107-014-0824-7zbMath1342.90163arXiv1405.4960OpenAlexW1877564947MaRDI QIDQ5962712
Publication date: 23 February 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1405.4960
Related Items
Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity ⋮ On a general framework for network representability in discrete optimization ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ The vertex \(k\)-cut problem ⋮ Uniform modular lattices and affine buildings ⋮ Unnamed Item ⋮ First-order logic axiomatization of metric graph theory ⋮ The Complexity of Valued CSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ A nonpositive curvature property of modular semilattices ⋮ A compact representation for modular semilattices and its applications ⋮ Unnamed Item ⋮ Polynomial combinatorial algorithms for skew-bisubmodular function minimization ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Minimum 0-extension problems on directed metrics ⋮ Weakly Modular Graphs and Nonpositive Curvature ⋮ A Tractable Class of Binary VCSPs via M-Convex Intersection ⋮ A survey of fundamental operations on discrete convex functions of various kinds
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of submodular function minimisation on diamonds
- Gated sets in metric spaces
- New algorithms for convex cost tension problem with application to computer vision
- Tight spans of distances and the dual fractionality of undirected multiflow problems
- Networks with Condorcet solutions
- Pseudomatroids
- Hereditary modular graphs
- Directed submodularity, ditroids and directed submodular flows
- Polyhedra related to undirected multicommodity flows
- Geometric algorithms and combinatorial optimization
- Discrete convex analysis
- Metrics with finite sets of primitive extensions
- Minimum 0-extensions of graph metrics
- A characterization of minimizable metrics in the multifacility location problem
- Notes on L-/M-convex functions and the separation theorems
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Proximity theorems of discrete convex functions
- Hard cases of the multifacility location problem
- A multifacility location problem on median spaces
- Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
- Graphs of some CAT(0) complexes
- Generalized skew bisubmodularity: a characterization and a min-max theorem
- One more well-solved case of the multifacility location problem
- Submodular functions and optimization.
- M-Convex Function on Generalized Polymatroid
- Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions
- Towards Minimizing k-Submodular Functions
- The Complexity of Finite-Valued CSPs
- Skew Bisubmodularity and Valued CSPs
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Folder Complexes and Multiflow Combinatorial Dualities
- Weakly Modular Graphs and Nonpositive Curvature
- Approximation algorithms for classification problems with pairwise relationships
- State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
- A Cut Approach to the Rectilinear Distance Facility Location Problem
- Modular Interval Spaces
- The Complexity of Multiterminal Cuts
- Semiring-based constraint satisfaction and optimization
- Multimatroids I. Coverings by Independent Sets
- Discrete Convex Analysis
- L-CONVEXITY ON GRAPH STRUCTURES
- The Complexity of Valued Constraint Satisfaction Problems
- The Maximum Multiflow Problems with Bounded Fractionality
- Oracle Tractability of Skew Bisubmodular Functions
- A Min-Max Theorem for Transversal Submodular Functions and Its Implications
- The Power of Linear Programming for General-Valued CSPs
- The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
- The complexity of conservative valued CSPs
