Permutohedra and minimal matrices |
| |
Institution: | 1. Technion, Israel Institute of Technology, 32000 Haifa, Israel;2. Instituto de Matemáticas, Unidad Morelia, UNAM, Apartado Postal 61-3, Xangari 58089, Morelia, Mich., Mexico |
| |
Abstract: | The notions of minimality, π-uniqueness and additivity originated in discrete tomography. They have applications to Kronecker products of characters of the symmetric group and arise as the optimal solutions of quadratic transportation problems. Here, we introduce the notion of real-minimality and give geometric characterizations of all these notions for a matrix A, by considering the intersection of the permutohedron determined by A with the transportation polytope in which A lies. We also study the computational complexity of deciding if the properties of being additive, real-minimal, π-unique and minimal hold for a given matrix, and show how to efficiently construct some matrix with any of these properties. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|