Please use this identifier to cite or link to this item: `http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17952`
DC FieldValueLanguage
dc.contributor.authorVasilakis, Emmanouil-
dc.date.accessioned2021-06-12T07:49:41Z-
dc.date.available2021-06-12T07:49:41Z-
dc.date.issued2021-
dc.identifier.urihttp://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17952-
dc.description.abstractIn 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.en_US
dc.languageenen_US
dc.subjectsubset sum, equal subset sum, k-subset sum, color-coding, fast fourier transformen_US
dc.titleImproved algorithms for subset sum problemsen_US
dc.description.pages78en_US
dc.contributor.supervisorΠαγουρτζής Αριστείδηςen_US
dc.departmentΤομέας Τεχνολογίας Πληροφορικής και Υπολογιστώνen_US
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat