摘要: Given a multiset S of n positive integers and target integer t, the subset sum problem is to decide if there that sums up t. We present new divide-and-conquer algorithm computes all realizable an u in [EQUATION], where σ elements O hides polylogarithmic factors. This result improves upon standard dynamic programming runs O(nu) time. To best our knowledge, fastest general deterministic for this problem. also modified finite cyclic groups, which within group [EQUATION] time, m order group.
arxiv.org
acm.org
harvard.edu
sci-hub.st 参考文章(23)
Takeaki Uno, Efficient Computation of Power Indices for Weighted Majority Games Algorithms and Computation. pp. 679- 689 ,(2012) , 10.1007/978-3-642-35261-4_70
Per Austrin, Petteri Kaski, Mikko Koivisto, Jussi Määttä, Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm Automata, Languages, and Programming. pp. 45- 56 ,(2013) , 10.1007/978-3-642-39206-1_5
Vijay Madisetti, The Digital Signal Processing Handbook CRC Press , IEEE Press. ,(2009) , 10.1201/9781482275193
E. Huang, R. E. Korf, Optimal rectangle packing: an absolute placement approach Journal of Artificial Intelligence Research. ,vol. 46, pp. 47- 87 ,(2013) , 10.1613/JAIR.3735
Van Vu, A Structural Approach to Subset-Sum Problems Bolyai Society Mathematical Studies. pp. 525- 545 ,(2008) , 10.1007/978-3-540-85221-6_19
U. Pferschy, Dynamic programming revisited: improving knapsack algorithms Computing. ,vol. 63, pp. 419- 430 ,(1999) , 10.1007/S006070050042
Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, Jacques Stern, Improved low-density subset sum algorithms Computational Complexity. ,vol. 2, pp. 111- 128 ,(1992) , 10.1007/BF01201999
Raphael Yuster, Yair Caro, The characterization of zero-sum (mod 2) bipartite Ramsey numbers Journal of Graph Theory. ,vol. 29, pp. 151- 166 ,(1998) , 10.1002/(SICI)1097-0118(199811)29:3<>1.0.CO;2-E
David Eppstein, Minimum Range Balanced Cuts via Dynamic Subset Sums Journal of Algorithms. ,vol. 23, pp. 375- 385 ,(1997) , 10.1006/JAGM.1996.0841
Éric Balandraud, Benjamin Girard, Simon Griffiths, Yahya ould Hamidoune, Subset sums in abelian groups The Journal of Combinatorics. ,vol. 34, pp. 1269- 1286 ,(2013) , 10.1016/J.EJC.2013.05.009