Discrete Convex Functions on Graphs and Their Algorithmic Applications
From MaRDI portal
Publication:4689627
DOI10.1007/978-981-10-6147-9_4zbMath1397.90237arXiv1706.09106OpenAlexW2730131851MaRDI QIDQ4689627
Publication date: 16 October 2018
Published in: Combinatorial Optimization and Graph Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.09106
Convex programming (90C25) Combinatorial optimization (90C27) Discrete location and assignment (90B80)
Related Items (7)
Uniform modular lattices and affine buildings ⋮ A nonpositive curvature property of modular semilattices ⋮ A compact representation for modular semilattices and its applications ⋮ Greedy systems of linear inequalities and lexicographically optimal solutions ⋮ Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings ⋮ A survey of fundamental operations on discrete convex functions of various kinds ⋮ A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of submodular function minimisation on diamonds
- New algorithms for the intersection problem of submodular systems
- Buildings of spherical type and finite BN-pairs
- Discrete convex analysis
- Minimum cost multiflows in undirected networks
- Minimum 0-extensions of graph metrics
- Notes on L-/M-convex functions and the separation theorems
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- Exact bounds for steepest descent algorithms of $L$-convex function minimization
- A multifacility location problem on median spaces
- Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
- A fast algorithm for the path 2-packing problem
- Bisubmodular polyhedra, simplicial divisions, and discrete convexity
- One more well-solved case of the multifacility location problem
- Submodular functions and optimization.
- Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation
- Half-integrality, LP-branching, and FPT Algorithms
- On a General Framework for Network Representability in Discrete Optimization
- The Generalized Terminal Backup Problem
- Recent Developments in Discrete Convex Analysis
- Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions
- Terminal Backup, 3D Matching, and Covering Cubic Graphs
- Lattice Theory: Foundation
- The Complexity of Finite-Valued CSPs
- Folder Complexes and Multiflow Combinatorial Dualities
- Approximation algorithms for classification problems with pairwise relationships
- Buildings
- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
- Some new results on node-capacitated packing of A-paths
- State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
- The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
- Modular Interval Spaces
- Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
- Discrete Convex Analysis
- ALGORITHMS FOR L-CONVEX FUNCTION MINIMIZATION: CONNECTION BETWEEN DISCRETE CONVEX ANALYSIS AND OTHER RESEARCH FIELDS
- L-CONVEXITY ON GRAPH STRUCTURES
- Multiway cuts in node weighted graphs
- The Complexity of Valued Constraint Satisfaction Problems
- The Power of Linear Programming for General-Valued CSPs
- Discrete convexity and polynomial solvability in minimum 0-extension problems
This page was built for publication: Discrete Convex Functions on Graphs and Their Algorithmic Applications
