On the complexity of variations of Equal Sum Subsets

Cieliebak, Mark; Eidenbenz, Stephan; Pagourtzis, Aris T.; Schlude, Konrad

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
Page(s):	151
Pages to:	172
Issue Date:	Sep-2008
Publisher / Ed. Institution:	Association for Computing Machinery
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.
URI:	https://dl.acm.org/doi/10.5555/1737763.1737764 https://digitalcollection.zhaw.ch/handle/11475/19064
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.

Show full item record

Cieliebak, M., Eidenbenz, S., Pagourtzis, A. T., & Schlude, K. (2008). On the complexity of variations of Equal Sum Subsets. Nordic Journal of Computing, 14(3), 151–172. https://dl.acm.org/doi/10.5555/1737763.1737764

Cieliebak, M. et al. (2008) ‘On the complexity of variations of Equal Sum Subsets’, Nordic Journal of Computing, 14(3), pp. 151–172. Available at: https://dl.acm.org/doi/10.5555/1737763.1737764.

M. Cieliebak, S. Eidenbenz, A. T. Pagourtzis, and K. Schlude, “On the complexity of variations of Equal Sum Subsets,” Nordic Journal of Computing, vol. 14, no. 3, pp. 151–172, Sep. 2008, [Online]. Available: https://dl.acm.org/doi/10.5555/1737763.1737764

CIELIEBAK, Mark, Stephan EIDENBENZ, Aris T. PAGOURTZIS und Konrad SCHLUDE, 2008. On the complexity of variations of Equal Sum Subsets. Nordic Journal of Computing [online]. September 2008. Bd. 14, Nr. 3, S. 151–172. Verfügbar unter: https://dl.acm.org/doi/10.5555/1737763.1737764

Cieliebak, Mark, Stephan Eidenbenz, Aris T. Pagourtzis, and Konrad Schlude. 2008. “On the Complexity of Variations of Equal Sum Subsets.” Nordic Journal of Computing 14 (3): 151–72. https://dl.acm.org/doi/10.5555/1737763.1737764.

Cieliebak, Mark, et al. “On the Complexity of Variations of Equal Sum Subsets.” Nordic Journal of Computing, vol. 14, no. 3, Sept. 2008, pp. 151–72, https://dl.acm.org/doi/10.5555/1737763.1737764.