CSpace  > 系统科学研究所
Solving low-density multiple subset sum problems with SVP oracle
Pan Yanbin; Zhang Feng
AbstractIt is well known that almost all subset sum problems with density less than 0.9408 center dot center dot center dot can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice. In this paper, the authors show that a similar result holds for the k-multiple subset sum problem which has k subset sum problems with exactly the same solution. Specially, for the single subset sum problem (k = 1), a modified lattice is introduced to make the proposed analysis much simpler and the bound for the success probability tighter than before. Moreover, some extended versions of the multiple subset sum problem are also considered.
KeywordLattice low-density multiple modular subset sum problem multiple subset sum problem
Funding ProjectNational Natural Science Foundation of China[11201458] ; National Natural Science Foundation of China[11471314] ; 973 Project[2011CB302401] ; National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of Sciences
WOS Research AreaMathematics
WOS SubjectMathematics, Interdisciplinary Applications
WOS IDWOS:000370162300014
Citation statistics
Document Type期刊论文
Corresponding AuthorPan Yanbin; Zhang Feng
AffiliationChinese Acad Sci, Acad Math & Syst Sci, NCMIS, Key Lab Math Mechanizat, Beijing 100190, Peoples R China
Recommended Citation
GB/T 7714
Pan Yanbin,Zhang Feng. Solving low-density multiple subset sum problems with SVP oracle[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,2016,29(1):228-242.
APA Pan Yanbin,&Zhang Feng.(2016).Solving low-density multiple subset sum problems with SVP oracle.JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,29(1),228-242.
MLA Pan Yanbin,et al."Solving low-density multiple subset sum problems with SVP oracle".JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY 29.1(2016):228-242.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Pan Yanbin]'s Articles
[Zhang Feng]'s Articles
Baidu academic
Similar articles in Baidu academic
[Pan Yanbin]'s Articles
[Zhang Feng]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Pan Yanbin]'s Articles
[Zhang Feng]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.