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

DOI10.1016/j.tcs.2007.09.030zbMath1161.68052OpenAlexW1988688790MaRDI 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

GCDcomputational complexityapproximation algorithmNP-hardprobabilistically checkable proofsnumber-theoretic problems

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)

Related Items (1)

An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm

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

This page was built for publication: An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))