|Publication type:||Article in scientific journal|
|Type of review:||Peer review (publication)|
|Title:||On the complexity of variations of Equal Sum Subsets|
|Authors :||Cieliebak, Mark|
Pagourtzis, Aris T.
|et. al :||No|
|Published in :||Nordic Journal of Computing|
|Publisher / Ed. Institution :||ACM|
|Subjects :||Equal Sum Subset|
|Subject (DDC) :||004: Computer science|
|Abstract:||The EQUAL SUM SUBSETS problem, where we are given a set of positive integers and we ask for two nonempty disjoint subsets such that their elements add up to the same total, is known to be NP-hard. In this paper we give (pseudo-)polynomial algorithms and/or (strong) NP-hardness proofs for several natural variations of EQUAL SUM SUBSETS. Among others we present (i) a framework for obtaining NP-hardness proofs and pseudopolynomial time algorithms for EQUAL SUM SUBSETS variations, which we apply to variants of the problem with additional selection restrictions, (ii) a proof of NP-hardness and a pseudo-polynomial time algorithm for the case where we ask for two subsets such that the ratio of their sums is some fixed rational r > 0, (iii) a pseudo-polynomial time algorithm for finding k subsets of equal sum, with k = O(1), and a proof of strong NP-hardness for the same problem with k = Ω(n), (iv) algorithms and hardness results for finding k equal sum subsets under the additional requirement that the subsets should be of equal cardinality. Our results are a step towards determining the dividing lines between polynomial time solvability, pseudo-polynomial time solvability, and strong NP-completeness of subset-sum related problems.|
|Fulltext version :||Published version|
|License (according to publishing contract) :||Licence according to publishing contract|
|Departement:||School of Engineering|
|Appears in Collections:||Publikationen School of Engineering|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.