Hardness of approximating the minimum solutions of linear Diophantine equations

DOI10.1016/J.TCS.2006.12.023MaRDI QIDQ1022600zbMATH OpenOpenAlexFDO

Authors Wenbin Chen, Jiangtao Meng

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

approximationcomputational complexitylinear Diophantine equationsNP-hardness

Mathematics Subject Classification ID

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

Recommendations

• New Hardness Results for Diophantine Approximation
• scientific article; zbMATH DE number 1114048
• An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
• Inapproximability results for the minimum integral solution problem with preprocessing over \(\ell_{\infty}\) norm
• The hardness of approximate optima in lattices, codes, and systems of linear equations

Cites work

• Approximating CVP to within almost-polynomial factors is NP-hard
• Efficient probabilistically checkable proofs and applications to approximations
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1088230 (Why is no real title available?)
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• The hardness of approximate optima in lattices, codes, and systems of linear equations

Cited in

(5)

• Inapproximability results for the minimum integral solution problem with preprocessing over \(\ell_{\infty}\) norm
• Lower bounds for solving linear diophantine equations on random access machines
• An extensive review of the literature using the Diophantine equations to study fuzzy set theory
• The complexity of almost linear diophantine problems
• An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1022600)