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
Eidenbenz, Stephan
Pagourtzis, Aris T.
Schlude, Konrad
et. al : No
Published in : Nordic Journal of Computing
Volume(Issue) : 14
Issue : 3
Pages : 151
Pages to: 172
Issue Date: Sep-2008
Publisher / Ed. Institution : ACM
ISSN: 1236-6064
Language : English
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.