Please use this identifier to cite or link to this item:
|Title:||Improved algorithms for subset sum problems|
|Keywords:||subset sum, equal subset sum, k-subset sum, color-coding, fast fourier transform|
|Abstract:||In this diploma dissertation, we present four pseudopolynomial time algorithms for the EQUAL SUBSET SUM problem, defined as follows: given a set Z of n positive integers, de- termine whether there exist two disjoint subsets of Z, the elements of which sum up to the same value. Assuming a given upper bound t > 0 on the sum of the two subsets, a standard dynamic programming approach can solve the problem in O(nt) time. We build on recent advances on SUBSET SUM due to Koiliaris and Xu [Koil19] and Bringmann [Brin17] in order to provide faster algorithms for EQUAL SUBSET SUM, and in particular for its search version, where a reconstruction of the solution sets is also sought. We devise three algorithms based on those advances: a randomised one of time complexity Õ(n + t), a deterministic one of Õ(σ) complexity and a deterministic Õ( √nt) time one, where σ is the total sum of the ele- ments of the input set. Additionally, we present a simple and efficient Õ(n + t) deterministic algorithm, which however does not seem to be able to be extended to more general problems. Inspired by these extensions, we further extend our techniques in order to cope with a more general variation of EQUAL SUBSET SUM, called k-SUBSET SUM, which asks for k disjoint subsets, whose elements sum up to a certain given value t i respectively. We propose two al- gorithms for the decision version of k-SUBSET SUM: one running in randomised Õ(n+t k ) time and a deterministic Õ(√n k/k+1 t k ) time respectively. We further demonstrate how these algo- rithms can be used to solve the decision versions of closely related variations of k-SUBSET SUM, namely SUBSET SUM RATiO, k-SUBSET SUM RATiO and MULTiPLE SUBSET SUM.|
|Appears in Collections:||Διπλωματικές Εργασίες - Theses|
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.