| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436910 | Theoretical Computer Science | 2007 | 5 Pages |
Abstract
Let 1≤p<∞ be any fixed real. We show that assuming P≠NP, it is hard to approximate the Minimum Solutions of Linear Diophantine Equations in ℓp norm within any constant factor and it is also hard to approximate the Minimum Solutions of Linear Diophantine Equations in ℓp norm within the factor nc/loglogn for some constant c>0 where n is the number of variables in the equations.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
