Approximating good simultaneous diophantine approximations is almost NP-hard

Rössner, Carsten ; Seifert, Jean-Pierre

2005

Online Electronic Resource

Access:

Zum Datensatz bei OAister, evt. Volltext

Given a real vector alpha =(alpha1 ; : : : ; alpha d ) and a real number E > 0 a good Diophantine approximation to alpha is a number Q such that IIQ alpha mod Zk1 ", where k \Delta k1 denotes the 1-norm kxk1 := max 1id jx i j for x = (x1 ; : : : ; xd ). Lagarias [12] proved the NP-completeness of the corresponding decision problem, i.e., given a vector ff 2 Q d , a rational number " ? 0 and a number N 2 N+ , decide whether there exists a number Q with 1 Q N and kQff mod Zk1 ". We prove that, unless ...

Title:	Approximating good simultaneous diophantine approximations is almost NP-hard
Author / Contributor:	Rössner, Carsten ; Seifert, Jean-Pierre
Link:	Zum Datensatz bei OAister, evt. Volltext
Publication:	2005
Media Type:	Electronic Resource
Subject heading:	Index Terms: ddc:510 report doc-type:report
Additional details:	Nachgewiesen in: OAIster Document Type: Electronic Resource Availability: Open access content. Open access content ; Deutsches Urheberrecht Note: application/pdf ; English Contributing Source: JOHANN WOLFGANG GOETHE UNIV ; From OAIster®, provided by the OCLC Cooperative.

Please select a fomat and save the data, next, you provide an e-mail address and have the data delivered there.

BibTeX Citavi, JabRef, et al.
(Reference Management)

PDF No full text!
(Notepad, Notes)

RIS Endnote, Citavi, e.a.
(Reference Management)

MODS
(XML for further processing)

Select the appropriate citation format, copy it to the clipboard, and have it sent by e-mail or save it as a PDF file.

Citation style selected:

Please check that the citation is formally correct prior to using it in a paper. You might like to use the "Export" dialogue for formatting citations yourself for a reference management program.