Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 1 of 50
Back to Result List

Test sets of the knapsack problem and simultaneous diophantine approximation

Please always quote using this URN: urn:nbn:de:0297-zib-2825
  • This paper deals with the study of test sets of the knapsack problem and simultaneous diophantine approximation. The Graver test set of the knapsack problem can be derived from minimal integral solutions of linear diophantine equations. We present best possible inequalities that must be satisfied by all minimal integral solutions of a linear diophantine equation and prove that for the corresponding cone the integer analogue of Caratheodory's theorem applies when the numbers are divisible. We show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. A recursive algorithm for computing this Hilbert basis is discussed. We also outline an algorithm for determining a Hilbert basis of a family of cones associated with the knapsack problem.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Martin Henk, Robert Weismantel
Document Type:ZIB-Report
Date of first Publication:1997/03/17
Series (Serial Number):ZIB-Report (SC-97-13)
ZIB-Reportnumber:SC-97-13
Published in:Appeared in: Algorithms - ESA 97 - 5th Annual European Symposium, Graz, 1997. R. Burkard, G. Woeginger (eds.) Springer, 1997. Lecture Notes in Computer Science 1284. Pp. 271-283
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.