Jump to ContentJump to Main Navigation
The Diophantine Frobenius Problem$
Users without a subscription are not able to see the full content.

Jorge L. Ramírez Alfonsín

Print publication date: 2005

Print ISBN-13: 9780198568209

Published to Oxford Scholarship Online: September 2007

DOI: 10.1093/acprof:oso/9780198568209.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 19 September 2020

Algorithmic aspects

Algorithmic aspects

(p.1) 1 Algorithmic aspects
The Diophantine Frobenius Problem

J. L. Ramírez Alfonsín

Oxford University Press

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.

Keywords:   algorithms, complexity, primitive matrix, graph theory, polynominal time

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .