The multidimensional Frobenius problem
type: Item
instance of: scholarly article
title: The multidimensional Frobenius problem
zbMATH Open document ID: 1243.11023
author: Jeffrey Amos
author: Iuliana Pascu
author: Vadim Ponomarenko
author: Enrique Treviño
author: Yan Zhang
published in: Involve
publication date: 2012-01-26T00:00:00Z
full work available at URL: p07.xhtml
review text: In this paper the authors consider a multidimensional analogue of the linear Diophantine problem of Frobenius. A numerical semigroup is a submonoid of the natural numbers with finite complement and the Frobenius problem is to determine the largest element of this complement. This paper focuses on a matrix generalization of this problem. Much of the difficulty in this paper consists of coming up with the appropriate adaptations of concepts from the classical one-dimensional setting to more general submonoids of \(\mathbb{N}_0^n\). Let M be an \(n \times (n+m)\) matrix with integer entries and \(x\) a length \(n\) column matrix with entries in \(\mathbb{N}_0\). The goal of this paper is to analyze the vectors \(g\) so that \(M x = g\) has no solutions. This leads to the study of linear combinations of these \(n+m\) columns with nonnegative coefficients. The authors define a partial order on vectors and define an appropriate notion of what it should mean for such a vector \(g\) to be maximal among those not in the monoid derived from \(M\). They then give higher-dimensional analogues of several results and techniques for one-dimensional Frobenius numbers in terms of these `Frobenius vectors'. In certain special cases they are able to give a complete characterization of this set of vectors.
reviewed by: Nathan Kaplan
Mathematics Subject Classification ID: 11D07
Mathematics Subject Classification ID: 11B75
Mathematics Subject Classification ID: 11D72
zbMATH DE Number: 6000329
zbMATH Keywords: Frobenius
zbMATH Keywords: coin-exchange
zbMATH Keywords: linear Diophantine system
MaRDI profile type: Publication
OpenAlex ID: W2160428704
DOI: 10.2140/INVOLVE.2011.4.187
description: scientific article; zbMATH DE number 6000329