Solving dense subset-sum problems by using analytical number theory

Mark Chaimovich, Gregory A. Freiman, Zvi Galil

Type: Article

Publication Date: 1989-09-01

Citations: 31

DOI: https://doi.org/10.1016/0885-064x(89)90025-3

View Publication

Locations

Journal of Complexity - View

Similar Works

Action	Title	Year	Authors
+	An almost linear-time algorithm for the dense subset-sum problem	1991	Zvi Galil Oded Margalit
+	An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem	1991	Zvi Galil Oded Margalit
+	Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach	2008	Changlin Wan Zhongzhi Shi
+	A branch bound method for subset sum problem	1994	Shiquan Wu
+	New analytical results in subset-sum problem	1993	Gregory A. Freiman
+	Approximating Subset Sum Ratio via Subset Sum Computations	2022	Giannis Alonistiotis Antonis Antonopoulos Nikolaos Melissinos Aris Pagourtzis Stavros Petsalakis Manolis Vasilakis
+ PDF Chat	Approximating Subset Sum Ratio via Subset Sum Computations	2022	Giannis Alonistiotis Antonis Antonopoulos Nikolaos Melissinos Aris Pagourtzis Stavros Petsalakis Manolis Vasilakis
+	A novel and efficient algorithm to solve subset sum problem	2020	B. Sinchev Askar Sinchev J. Akzhanova A. M. Mukhanova Y. Issekeshev
+	A Subset-Sum Inequality: 11100	2006	Călin Popescu Richard Stong
+ PDF Chat	On the Two-Dimensional Subset Sum Problem	2018	Alain Plagne
+	Fractal Analysis of the Subset-Sum Problem	2024	Ruben Horn Daan van den Berg Pieter Adriaans
+	A Probabilistic Approach to The Perfect Sum Problem	2022	Kristof Pusztai
+ PDF Chat	Revisiting the Random Subset Sum problem	2022	Arthur da Cunha Francesco d’Amore Frédéric Giroire Hicham Lesfari Emanuele Natale Laurent Viennot
+ PDF Chat	Integer factorization as subset-sum problem	2023	Markus Hittmeir
+	On variations of the subset sum problem	1998	Jorge L. Ramírez Alfonsín
+ PDF Chat	Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm	2013	Per Austrin Petteri Kaski Mikko Koivisto Jussi Määttä
+	Worst-Case Analysis of Some Algorithms for Solving the Subset-Sum Problem	1996	Yu. V. Shamardin
+	The subset sum problem and arithmetic coding	1995	Sean A. Irvine John G. Cleary Ingrid Rinsma-Melchert
+ PDF Chat	Approximation Schemes for Subset Sum Ratio Problems	2020	Nikolaos Melissinos Aris Pagourtzis Theofilos Triommatis
+	Approximating Subset Sum Ratio via Partition Computations	2022	Giannis Alonistiotis Antonis Antonopoulos Nikolaos Melissinos Aris Pagourtzis Stavros Petsalakis Manolis Vasilakis

Works That Cite This (14)

Action	Title	Year	Authors
+	On Solvability of a System of Two Boolean Linear Equations	1996	Gregory A. Freiman
+	Bisecting binomial coefficients	2017	Eugen J. Ionaşcu Thor Martinsen Pantelimon Stănică
+	Bisecting binomial coefficients	2016	Eugen J. Ionaşcu Thor Martinsen Pantelimon Stănică
+	Phase transition and finite‐size scaling for the integer partitioning problem	2001	Christian Borgs Jennifer Chayes Boris Pittel
+	Sharp threshold and scaling window for the integer partitioning problem	2001	Christian Borgs Jennifer Chayes Boris Pittel
+	An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem	1991	Zvi Galil Oded Margalit
+	An almost linear-time algorithm for the dense subset-sum problem	1991	Zvi Galil Oded Margalit
+	Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach	2008	Changlin Wan Zhongzhi Shi
+ PDF Chat	Ternary Syndrome Decoding with Large Weight	2020	Rémi Bricout André Chailloux Thomas Debris-Alazard Matthieu Lequesne
+ PDF Chat	Ternary Syndrome Decoding with Large Weight	2019	Rémi Bricout André Chailloux Thomas Debris-Alazard Matthieu Lequesne

Works Cited by This (6)

Action	Title	Year	Authors
+ PDF Chat	On representation of r-th powers by subset sums	1989	E. Lipkin
+	Finite addition theorems, I	1989	Andràs Sárközy
+	AN EFFECTIVE FORMULA FOR THE NUMBER OF SOLUTIONS OF A SYSTEM OF 0, 1 LINEAR EQUATIONS	1983	P. L. Buzytsky Gregory A. Freiman
+ PDF Chat	On sums of subsets of a set of integers	1988	N. Alon Gregory A. Freiman
+	ON FOUNDATIONS OF CONVEX ANALYSIS	1980	A. D. Ioffe
+	On two additive problems	1990	P. Erdős Gregory A. Freiman