Hardness of approximating the minimum solutions of linear Diophantine equations

DOI10.1016/j.tcs.2006.12.023zbMath1164.68007OpenAlexW2076437991MaRDI QIDQ1022600

Jiangtao Meng, Wenbin Chen

Publication date: 22 June 2009

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

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

zbMATH Keywords

computational complexityapproximationlinear Diophantine equationsNP-hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Linear Diophantine equations (11D04)

Related Items (1)

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

Cites Work

• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Approximating CVP to within almost-polynomial factors is NP-hard
• Efficient probabilistically checkable proofs and applications to approximations
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hardness of approximating the minimum solutions of linear Diophantine equations