| Publikationstyp: | Beitrag in wissenschaftlicher Zeitschrift |
| Art der Begutachtung: | Peer review (Publikation) |
| Titel: | On the complexity of variations of Equal Sum Subsets |
| Autor/-in: | Cieliebak, Mark Eidenbenz, Stephan Pagourtzis, Aris T. Schlude, Konrad |
| et. al: | No |
| Erschienen in: | Nordic Journal of Computing |
| Band(Heft): | 14 |
| Heft: | 3 |
| Seite(n): | 151 |
| Seiten bis: | 172 |
| Erscheinungsdatum: | Sep-2008 |
| Verlag / Hrsg. Institution: | Association for Computing Machinery |
| ISSN: | 1236-6064 |
| Sprache: | Englisch |
| Schlagwörter: | Equal Sum Subset |
| Fachgebiet (DDC): | 004: Informatik |
| Zusammenfassung: | 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 |
| Volltext Version: | Publizierte Version |
| Lizenz (gemäss Verlagsvertrag): | Lizenz gemäss Verlagsvertrag |
| Departement: | School of Engineering |
| Enthalten in den Sammlungen: | Publikationen School of Engineering |
Dateien zu dieser Ressource:
Es gibt keine Dateien zu dieser Ressource.
Zur Langanzeige
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.
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.