1. ZHAW digitalcollection
  2. School of Engineering
  3. Publikationen
  4. Publikationen School of Engineering
Full metadata record
DC FieldValueLanguage
dc.contributor.authorCieliebak, Mark-
dc.contributor.authorEidenbenz, Stephan-
dc.contributor.authorPagourtzis, Aris T.-
dc.contributor.authorSchlude, Konrad-
dc.date.accessioned2020-01-09T11:56:08Z-
dc.date.available2020-01-09T11:56:08Z-
dc.date.issued2008-09-
dc.identifier.issn1236-6064de_CH
dc.identifier.urihttps://dl.acm.org/doi/10.5555/1737763.1737764de_CH
dc.identifier.urihttps://digitalcollection.zhaw.ch/handle/11475/19064-
dc.description.abstractThe 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.de_CH
dc.language.isoende_CH
dc.publisherAssociation for Computing Machineryde_CH
dc.relation.ispartofNordic Journal of Computingde_CH
dc.rightsLicence according to publishing contractde_CH
dc.subjectEqual Sum Subsetde_CH
dc.subject.ddc004: Informatikde_CH
dc.titleOn the complexity of variations of Equal Sum Subsetsde_CH
dc.typeBeitrag in wissenschaftlicher Zeitschriftde_CH
dcterms.typeTextde_CH
zhaw.departementSchool of Engineeringde_CH
zhaw.funding.euNode_CH
zhaw.issue3de_CH
zhaw.originated.zhawNode_CH
zhaw.pages.end172de_CH
zhaw.pages.start151de_CH
zhaw.publication.statuspublishedVersionde_CH
zhaw.volume14de_CH
zhaw.publication.reviewPeer review (Publikation)de_CH
zhaw.webfeedNatural Language Processingde_CH
zhaw.author.additionalNode_CH
Appears in collections:Publikationen School of Engineering

Files in This Item:
There are no files associated with this item.
Show simple 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.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.