A fast and simple algorithm for the Money Changing Problem. Böcker, S. & Lipták, e. Algorithmica, 48(4):413–432, 2007. doi abstract bibtex The Money Changing Problem (MCP) can be stated as follows: Given $k$ positive integers $a_1< … < a_k$ and a query integer $M$, is there a linear combination $∑_i c_ia_i = M$ with non-negative integers $c_i$, a \emphdecomposition of $M$? If so, produce one or all such decompositions. The largest integer without such a decomposition is called the \emphFrobenius number $g(a_1,…,a_k)$. A data structure called \em residue table of $a_1$ words can be used to compute the Frobenius number in time $O(a_1)$. We present an intriguingly simple algorithm for computing the residue table which runs in time $O(ka_1)$, with no additional memory requirements, outperforming the best previously known algorithm. Simulations show that it performs well even on 'hard' instances from the literature. In addition, we can employ the residue table to answer MCP decision instances in constant time, and a slight modification of size $O(a_1)$ to compute one decomposition for a query $M$. Note that since both, computing the Frobenius number and MCP (decision) are NP-hard, one cannot expect to find an algorithm that is polynomial in the size of the input, i.e., in $k,łog a_k$, and $łog M$. We then give an algorithm which, using a modification of the residue table, also constructible in $O(ka_1)$ time, computes all decompositions of a query integer $M$. Its worst-case running time is $O(ka_1)$ for each decomposition, thus the total runtime depends only on the output size and is independent of the size of query $M$ itself. We apply our latter algorithm to interpreting mass spectrometry (MS) peaks: Due to its high speed and accuracy, MS is now the method of choice in protein identification. Interpreting individual peaks is one of the recurring subproblems in analyzing MS data; the task is to identify sample molecules whose mass the peak possibly represents. This can be stated as an MCP instance, with the masses of the individual amino acids as the $k$ integers $a_1,…, a_k$. Our simulations show that our algorithm is fast on real data and is well suited for generating candidates for peak interpretation.
@Article{boecker07fast,
author = {Sebastian B\"ocker and {\relax Zs}uzsanna Lipt{\'a}k},
title = {A fast and simple algorithm for the {Money Changing Problem}},
journal = {Algorithmica},
year = {2007},
volume = {48},
number = {4},
pages = {413--432},
abstract = {The Money Changing Problem (MCP) can be stated as follows: Given $k$ positive integers $a_1< \ldots < a_k$ and a query integer $M$, is there a linear combination $\sum_i c_ia_i = M$ with non-negative integers $c_i$, a \emph{decomposition} of $M$? If so, produce one or all such decompositions. The largest integer without such a decomposition is called the \emph{Frobenius number} $g(a_1,\ldots,a_k)$. A data structure called {\em residue table} of $a_1$ words can be used to compute the Frobenius number in time $O(a_1)$. We present an intriguingly simple algorithm for computing the residue table which runs in time $O(ka_1)$, with no additional memory requirements, outperforming the best previously known algorithm. Simulations show that it performs well even on 'hard' instances from the literature. In addition, we can employ the residue table to answer MCP decision instances in constant time, and a slight modification of size $O(a_1)$ to compute one decomposition for a query $M$. Note that since both, computing the Frobenius number and MCP (decision) are NP-hard, one cannot expect to find an algorithm that is polynomial in the size of the input, i.e., in $k,\log a_k$, and $\log M$. We then give an algorithm which, using a modification of the residue table, also constructible in $O(ka_1)$ time, computes all decompositions of a query integer $M$. Its worst-case running time is $O(ka_1)$ for each decomposition, thus the total runtime depends only on the output size and is independent of the size of query $M$ itself. We apply our latter algorithm to interpreting mass spectrometry (MS) peaks: Due to its high speed and accuracy, MS is now the method of choice in protein identification. Interpreting individual peaks is one of the recurring subproblems in analyzing MS data; the task is to identify sample molecules whose mass the peak possibly represents. This can be stated as an MCP instance, with the masses of the individual amino acids as the $k$ integers $a_1,\ldots, a_k$. Our simulations show that our algorithm is fast on real data and is well suited for generating candidates for peak interpretation.},
doi = {10.1007/s00453-007-0162-8},
file = {BoeckerLiptak_FastSimpleAlgorithmMoneyChanging_Algorithmica_2007.pdf:2007/BoeckerLiptak_FastSimpleAlgorithmMoneyChanging_Algorithmica_2007.pdf:PDF},
keywords = {jena; IDUN; linkpdf; frobenius},
owner = {Sebastian},
timestamp = {2006.10.17},
}
Downloads: 0
{"_id":"ZC9K7WzDLCA5KKpMa","bibbaseid":"bcker-liptk-afastandsimplealgorithmforthemoneychangingproblem-2007","authorIDs":[],"author_short":["Böcker, S.","Lipták, e."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Sebastian"],"propositions":[],"lastnames":["Böcker"],"suffixes":[]},{"firstnames":["e̊lax Zsuzsanna"],"propositions":[],"lastnames":["Lipták"],"suffixes":[]}],"title":"A fast and simple algorithm for the Money Changing Problem","journal":"Algorithmica","year":"2007","volume":"48","number":"4","pages":"413–432","abstract":"The Money Changing Problem (MCP) can be stated as follows: Given $k$ positive integers $a_1< … < a_k$ and a query integer $M$, is there a linear combination $∑_i c_ia_i = M$ with non-negative integers $c_i$, a \\emphdecomposition of $M$? If so, produce one or all such decompositions. The largest integer without such a decomposition is called the \\emphFrobenius number $g(a_1,…,a_k)$. A data structure called \\em residue table of $a_1$ words can be used to compute the Frobenius number in time $O(a_1)$. We present an intriguingly simple algorithm for computing the residue table which runs in time $O(ka_1)$, with no additional memory requirements, outperforming the best previously known algorithm. Simulations show that it performs well even on 'hard' instances from the literature. In addition, we can employ the residue table to answer MCP decision instances in constant time, and a slight modification of size $O(a_1)$ to compute one decomposition for a query $M$. Note that since both, computing the Frobenius number and MCP (decision) are NP-hard, one cannot expect to find an algorithm that is polynomial in the size of the input, i.e., in $k,łog a_k$, and $łog M$. We then give an algorithm which, using a modification of the residue table, also constructible in $O(ka_1)$ time, computes all decompositions of a query integer $M$. Its worst-case running time is $O(ka_1)$ for each decomposition, thus the total runtime depends only on the output size and is independent of the size of query $M$ itself. We apply our latter algorithm to interpreting mass spectrometry (MS) peaks: Due to its high speed and accuracy, MS is now the method of choice in protein identification. Interpreting individual peaks is one of the recurring subproblems in analyzing MS data; the task is to identify sample molecules whose mass the peak possibly represents. This can be stated as an MCP instance, with the masses of the individual amino acids as the $k$ integers $a_1,…, a_k$. Our simulations show that our algorithm is fast on real data and is well suited for generating candidates for peak interpretation.","doi":"10.1007/s00453-007-0162-8","file":"BoeckerLiptak_FastSimpleAlgorithmMoneyChanging_Algorithmica_2007.pdf:2007/BoeckerLiptak_FastSimpleAlgorithmMoneyChanging_Algorithmica_2007.pdf:PDF","keywords":"jena; IDUN; linkpdf; frobenius","owner":"Sebastian","timestamp":"2006.10.17","bibtex":"@Article{boecker07fast,\n author = {Sebastian B\\\"ocker and {\\relax Zs}uzsanna Lipt{\\'a}k},\n title = {A fast and simple algorithm for the {Money Changing Problem}},\n journal = {Algorithmica},\n year = {2007},\n volume = {48},\n number = {4},\n pages = {413--432},\n abstract = {The Money Changing Problem (MCP) can be stated as follows: Given $k$ positive integers $a_1< \\ldots < a_k$ and a query integer $M$, is there a linear combination $\\sum_i c_ia_i = M$ with non-negative integers $c_i$, a \\emph{decomposition} of $M$? If so, produce one or all such decompositions. The largest integer without such a decomposition is called the \\emph{Frobenius number} $g(a_1,\\ldots,a_k)$. A data structure called {\\em residue table} of $a_1$ words can be used to compute the Frobenius number in time $O(a_1)$. We present an intriguingly simple algorithm for computing the residue table which runs in time $O(ka_1)$, with no additional memory requirements, outperforming the best previously known algorithm. Simulations show that it performs well even on 'hard' instances from the literature. In addition, we can employ the residue table to answer MCP decision instances in constant time, and a slight modification of size $O(a_1)$ to compute one decomposition for a query $M$. Note that since both, computing the Frobenius number and MCP (decision) are NP-hard, one cannot expect to find an algorithm that is polynomial in the size of the input, i.e., in $k,\\log a_k$, and $\\log M$. We then give an algorithm which, using a modification of the residue table, also constructible in $O(ka_1)$ time, computes all decompositions of a query integer $M$. Its worst-case running time is $O(ka_1)$ for each decomposition, thus the total runtime depends only on the output size and is independent of the size of query $M$ itself. We apply our latter algorithm to interpreting mass spectrometry (MS) peaks: Due to its high speed and accuracy, MS is now the method of choice in protein identification. Interpreting individual peaks is one of the recurring subproblems in analyzing MS data; the task is to identify sample molecules whose mass the peak possibly represents. This can be stated as an MCP instance, with the masses of the individual amino acids as the $k$ integers $a_1,\\ldots, a_k$. Our simulations show that our algorithm is fast on real data and is well suited for generating candidates for peak interpretation.},\n doi = {10.1007/s00453-007-0162-8},\n file = {BoeckerLiptak_FastSimpleAlgorithmMoneyChanging_Algorithmica_2007.pdf:2007/BoeckerLiptak_FastSimpleAlgorithmMoneyChanging_Algorithmica_2007.pdf:PDF},\n keywords = {jena; IDUN; linkpdf; frobenius},\n owner = {Sebastian},\n timestamp = {2006.10.17},\n}\n\n","author_short":["Böcker, S.","Lipták, e."],"key":"boecker07fast","id":"boecker07fast","bibbaseid":"bcker-liptk-afastandsimplealgorithmforthemoneychangingproblem-2007","role":"author","urls":{},"keyword":["jena; IDUN; linkpdf; frobenius"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:29:35.075Z","downloads":0,"keywords":["jena; idun; linkpdf; frobenius"],"search_terms":["fast","simple","algorithm","money","changing","problem","böcker","lipták"],"title":"A fast and simple algorithm for the Money Changing Problem","year":2007,"dataSources":["C5FtkvWWggFfMJTFX"]}