We present a variety of exact and parameterized algorithms for Subset Sum and otherrelated problems. The major contributions of this thesis include:
1. Average-case algorithms for Generalized Subset Sum, the problem that generalizes both Subset Sum and Equal Subset Sum, as well as structural results describing the parameter regime in which solutions exist. These results extend the application of the “Representation Method” and are the fastest known in this setting.
2. A proof that Either-Or Subset Sum, the problem of solving either Subset Sum or Equal Subset Sum, can be solved exponentially faster than time 2⁰‧⁵ⁿ in the worst case. In our view, this result illustrates the potential of the “structure vs. randomness” approach for Subset Sum.
3. Algorithms that solve worst-case Subset Sum faster than time 2⁰‧⁵ⁿ by a polynomial factor. These improvements on the best known exact algorithms for Subset Sum represent the successful application of “log shaving” techniques to the problem.
4. Algorithms for Subset Sum and k-SUM with constant doubling. When considered in terms of a novel parameterization in the doubling constant, Subset Sum admits an XP-algorithm, while k-SUM is Fixed-Parameter Tractable. We also show that Subset Sum is FPT in the doubling constant if and only if an instance I of Hyperplane-Constrained Integer Linear Programming with n variables, m constraints, and constraint matrix entries bounded by ∆ can be solved in time ∆^{O(m)} · poly(|I|).
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/baym-5m55 |
| Date | January 2024 |
| Creators | Randolph, Timothy William |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0025 seconds