A Structural Approach to Subset-Sum Problems

DOI10.1007/978-3-540-85221-6_19zbMATH Open1169.11012arXiv0804.3211OpenAlexW1832165767MaRDI QIDQ3601935FDOQ3601935

Authors: Van Vu 

Publication date: 12 February 2009

Published in: Bolyai Society Mathematical Studies (Search for Journal in Brave)

Abstract: We discuss a structural approach to subset-sum problems in additive combinatorics. The core of this approach are Freiman-type structural theorems, many of which will be presented through the paper. These results have applications in various areas, such as number theory, combinatorics and mathematical physics.

Full work available at URL: https://arxiv.org/abs/0804.3211

Recommendations

• Structural approach to subset sum problems
• Long arithmetic progressions in sumsets: Thresholds and bounds
• scientific article; zbMATH DE number 1315256
• scientific article; zbMATH DE number 1315254
• Finite and infinite arithmetic progressions in sumsets

zbMATH Keywords

random matricessubset-sumErdős-Ginzburg-Ziv theoremCircular LawFolkman's conjectureFreiman-type structural theoreminverse Little\-wood-Offord theoremsquare-sum free setzero-sum-free sets

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Additive bases, including sumsets (11B13)

Cited In (8)

• New analytical results in subset-sum problem
• A Structure Theory for the Parametric Submodular Intersection Problem
• On a conjecture of Alon
• Solving dense subset-sum problems by using analytical number theory
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Subset sum problems with digraph constraints
• Improved approximation of linear threshold functions
• Approximability of the Subset Sum Reconfiguration Problem

This page was built for publication: A Structural Approach to Subset-Sum Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3601935)