*J. L. Ramírez Alfonsín*

- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198568209
- eISBN:
- 9780191718229
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198568209.003.0001
- Subject:
- Mathematics, Algebra, Combinatorics / Graph Theory / Discrete Mathematics

This chapter is devoted to the computational aspects of the Frobenius number. After discussing a number of methods to solve FP when n = 3 (some of these procedures make use of diverse concepts, such ...
More

This chapter is devoted to the computational aspects of the Frobenius number. After discussing a number of methods to solve FP when n = 3 (some of these procedures make use of diverse concepts, such as the division remainder, continued fractions and maximal lattice free bodies) it presents a variety of algorithms to compute g(a1, . . . , an) for general n. The main ideas of these algorithms are based on concepts from graph theory, index of primitivity of non-negative matrices, and mathematical programming. While the running times of these algorithms are super-polynomial, there exists a method, due to R. Kannan, that solves FP in polynomial time for any fixed n. This method is described, in which the covering radius concept is introduced. The chapter ends by proving that FP is NP-hard under Turing reductions.Less

This chapter is devoted to the computational aspects of the Frobenius number. After discussing a number of methods to solve **FP** when n = 3 (some of these procedures make use of diverse concepts, such as the division remainder, continued fractions and maximal lattice free bodies) it presents a variety of algorithms to compute g(a1, . . . , an) for general n. The main ideas of these algorithms are based on concepts from graph theory, index of primitivity of non-negative matrices, and mathematical programming. While the running times of these algorithms are super-polynomial, there exists a method, due to R. Kannan, that solves **FP** in polynomial time for any fixed n. This method is described, in which the covering radius concept is introduced. The chapter ends by proving that **FP** is NP-hard under Turing reductions.