Approximating the SVP to within a Factor (1+1/dim<sup>ε</sup>) Is NP-Hard under Randomized Reductions.

CAI J-Y; NERURKAR A

Art

J-GLOBAL ID：200902188542676621 Reference number：99A1028271

Approximating the SVP to within a Factor (1+1/dim^ε) Is NP-Hard under Randomized Reductions.

SVPの因子(1+1/dim^ε)内での近似はダンラムな縮約のもとでNP困難である

Publisher site Copy service {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=99A1028271&COPY=1") }}
Access JDreamⅢ for advanced search and analysis. {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=99A1028271&from=J-GLOBAL&jstjournalNo=B0861A") }}

Author (2)： ,
Material：
Volume： 59 Issue： 2 Page： 221-239 Publication year： Oct. 1999
JST Material Number： B0861A ISSN： 0022-0000 Document type： Article
Article type：原著論文 Country of issue： Netherlands (NLD) Language： ENGLISH (EN)

,...

To see more with JDream III (charged). {{ this.onShowAbsJLink("http://jdream3.com/lp/jglobal/index.html?docNo=99A1028271&from=J-GLOBAL&jstjournalNo=B0861A") }}

Theory of computation

, , , ,

Return to Previous Page

Approximating the SVP to within a Factor (1+1/dimε) Is NP-Hard under Randomized Reductions.

Approximating the SVP to within a Factor (1+1/dim^ε) Is NP-Hard under Randomized Reductions.