An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))
type: Item
instance of: scholarly article
title: An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))
zbMATH Open document ID: 1161.68052
author: Wenbin Chen
author: Jiangtao Meng
author: Dengpan Yin
published in: Theoretical Computer Science
publication date: 2008-05-28T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 11A05
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5279819
zbMATH Keywords: approximation algorithm
zbMATH Keywords: computational complexity
zbMATH Keywords: GCD
zbMATH Keywords: NP-hard
zbMATH Keywords: number-theoretic problems
zbMATH Keywords: probabilistically checkable proofs
MaRDI profile type: Publication
full work available at URL: j.tcs.2007.09.030
OpenAlex ID: W1988688790
cites work: A note on equivalent systems of linear diophantine equations
cites work: Q3002852
cites work: Approximate solution of NP optimization problems
cites work: Q3726125
cites work: Hardness of approximating the minimum solutions of linear Diophantine equations
cites work: The complexity of theorem-proving procedures
cites work: Approximating CVP to within almost-polynomial factors is NP-hard
cites work: Interactive proofs and the hardness of approximating cliques
cites work: Q4862236
cites work: Integer matrix diagonalization
cites work: Q4941893
cites work: 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
cites work: Polynomial-Time Aggregation of Integer Programming Problems
cites work: Q4142699
cites work: Q4847928
cites work: Q4375622
cites work: A hard problem that is almost always easy
DOI: 10.1016/J.TCS.2007.09.030
description: scientific article; zbMATH DE number 5279819