wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

subset_sum (824B)

      1 # Subset sum
      2 
      3 given integers S and a target t, can we achieve t exactly as a sum of a subset of elements of S?
      4 
      5 [np_complete], admits [pseudo_polynomial_time] algorithm
      6   - faster [pseudo_polynomial_time] algorithm: [chen2024improved]
      7 
      8 special case: [partition_problem]
      9 
     10 [reduction]s:
     11 - [reduction_sat_subset_sum] from [satisfiability_boolean] on [conjunctive_normal_form]
     12 - [reduction_3dm_subset_sum] from [3_dimensional_matching]
     13 
     14 [algorithms]:
     15 - [galil1991almost] for dense subset sum
     16   - further analysis in [bringmann2021near]
     17 - [bringmann2017near] which is [randomized_algorithm]
     18 
     19 generalization: [all_subset_sums], compute all the sums
     20 - according to [bringmann2023top], all [pseudo_polynomial_time] algorithms for subset sum actually solve [all_subset_sums]
     21 
     22 - [subset_sum_counting]
     23 
     24 Up: [decision_problem] on [sum]