An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\)

DOI10.1016/j.ipl.2006.09.005zbMath1185.68850OpenAlexW1585437534MaRDI QIDQ845926

Wenbin Chen, Jiangtao Meng

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.09.005

zbMATH Keywords

computational complexityapproximation algorithmDiophantine approximationNP-hardhomogeneous linear systeminteger relation

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Cites Work

• On the hardness of approximating shortest integer relations among rational numbers
• Approximating CVP to within almost-polynomial factors is NP-hard
• Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• Unnamed Item
• Unnamed Item

This page was built for publication: An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\)