An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))

DOI10.1016/j.tcs.2007.09.030zbMath1161.68052MaRDI QIDQ924126

Wenbin Chen, Jiangtao Meng, Dengpan Yin

Publication date: 28 May 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.09.030

zbMATH Keywords

GCD; computational complexity; approximation algorithm; NP-hard; probabilistically checkable proofs; number-theoretic problems

Mathematics Subject Classification ID

11Y16: Number-theoretic algorithms; complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

11A05: Multiplicative structure; Euclidean algorithm; greatest common divisors

Cites Work

• Approximate solution of NP optimization problems
• Hardness of approximating the minimum solutions of linear Diophantine equations
• Integer matrix diagonalization
• Approximating CVP to within almost-polynomial factors is NP-hard
• Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix
• Polynomial-Time Aggregation of Integer Programming Problems
• Interactive proofs and the hardness of approximating cliques
• The complexity of theorem-proving procedures
• A note on equivalent systems of linear diophantine equations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item