Minimum 0-extension problems on directed metrics

DOI10.1016/j.disopt.2021.100642zbMath1506.68038arXiv2006.00153OpenAlexW3142849537MaRDI QIDQ2042078

Hiroshi Hirai, Ryuhei Mizutani

Publication date: 27 July 2021

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.00153

zbMATH Keywords

computational complexityvalued constraint satisfaction problemsdirected metricsminimum 0-extension problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Tight spans of distances and the dual fractionality of undirected multiflow problems
• Networks with Condorcet solutions
• Metrics with finite sets of primitive extensions
• Minimum 0-extensions of graph metrics
• Hard cases of the multifacility location problem
• A multifacility location problem on median spaces
• One more well-solved case of the multifacility location problem
• The complexity of soft constraint satisfaction
• The Complexity of Finite-Valued CSPs
• Folder Complexes and Multiflow Combinatorial Dualities
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• Modular Interval Spaces
• The Complexity of Multiterminal Cuts
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimum 0-extension problems on directed metrics