On a property of a three-dimensional matrix
Summary: Let \(S_n\) be the symmetrical group acting on the set \(\{1,2,\dots,n\}\) and \(x, y\in S_n\). Consider the set \(W=\{(i,x(i), y(i))\;|\;1\leq i\leq n,\;|i-x(i)|>1\vee |i-y(i)|>1\vee|x(i)-y(i)|>1\}\). The main result of this paper is the following theorem. If the number of \(W\) set entries is more than \([n/3]\), then there exist entries \((i_1,x(i_1),y(i_1)), (i_2,x(i_2),y(i_2)), (i_3,x(i_3),y(i_3))\in W\) such that \(|i_1-x(i_2)|\leq 1\), \(|i_1-y(i_3)|\leq 1\), and \(|x(i_2)-y(i_3)|\leq 1\). The application of this theorem to the three-dimensional assignment problem is considered.
- A Monge property for the \(d\)-dimensional transportation problem
- An Algorithm for the Three-Index Assignment Problem
- An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices
- Approximation algorithms for three-dimensional assignment problems with triangle inequalities
- Assignment problem for three-index Jacobi matrices
- Cubic Matrices, Generalized Spin Algebra and Uncertainty Relation
- Generalizations of suffix arrays to multi-dimensional matrices.
- Geometric three-dimensional assignment problems
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Letter to the Editor—The Multidimensional Assignment Problem
- Lower bounds for the axial three-index assignment problem
- Maximizing traveling salesman problem for special matrices
- On the Plane Term Rank of a Three Dimensional Matrix
- On the plane term rank of three dimensional matrices
- Three-dimensional axial assignment problems with decomposable cost coefficients
- Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems
This page was built for publication: On a property of a three-dimensional matrix
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249936)
