The three-dimensional matching problem in kalmanson matrices

DOI10.1007/S10878-011-9426-YMaRDI QIDQ358634zbMATH OpenOpenAlexFDO

Authors Frits C. R. Spieksma, Gerhard J. Woeginger, S. Polyakovskiy

Publication date 9 August 2013

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s10878-011-9426-y

zbMATH Keywords

computational complexitycombinatorial optimizationtractable case

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Publication:4953913
• The Steiner tree problem in Kalmanson matrices and in circulant matrices
• scientific article; zbMATH DE number 1202983
• Approximation algorithms for three-dimensional assignment problems with triangle inequalities
• Certain NP-complete matching problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A canonical decomposition theory for metrics on a finite set
• A note on circular decomposable metrics
• A solvable case of the quadratic assignment problem
• Approximation algorithms for three-dimensional assignment problems with triangle inequalities
• Edgeconvex Circuits and the Traveling Salesman Problem
• Geometric three-dimensional assignment problems
• Reducibility among combinatorial problems
• Sometimes Travelling is Easy: The Master Tour Problem
• The Steiner tree problem in Kalmanson matrices and in circulant matrices
• The structure of circular decomposable metrics

Cited in

(5)

• Recognising permuted Demidenko matrices
• The multi-stripe travelling salesman problem
• Four-point conditions for the TSP: the complete complexity classification
• A new tractable case of the QAP with a Robinson matrix
• New special cases of the quadratic assignment problem with diagonally structured coefficient matrices

This page was built for publication: The three-dimensional matching problem in kalmanson matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q358634)