On the equal-subset-sum problem

G.J. Woeginger; Zhongliang Yu

doi:10.1016/0020-0190(92)90226-L

On the equal-subset-sum problem

G.J. Woeginger, Zhongliang Yu

Research output: Contribution to journal › Article › Academic › peer-review

52 Citations (Scopus)

Abstract

Given a set S of n integers, the problem is to decide whether there exist two disjoint nonempty subsets S1,S2S whose elements sum up to the same value. We show this problem to be NP-complete and we present an approximation algorithm with worst-case ratio 1.324 for the optimization version of this problem.

Original language	English
Pages (from-to)	299-302
Journal	Information Processing Letters
Volume	42
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(92)90226-L
Publication status	Published - 1992

Access to Document

10.1016/0020-0190(92)90226-L

Cite this

@article{8691cd3cc4ea4549a03c33bbe80ffdd1,

title = "On the equal-subset-sum problem",

abstract = "Given a set S of n integers, the problem is to decide whether there exist two disjoint nonempty subsets S1,S2S whose elements sum up to the same value. We show this problem to be NP-complete and we present an approximation algorithm with worst-case ratio 1.324 for the optimization version of this problem.",

author = "G.J. Woeginger and Zhongliang Yu",

year = "1992",

doi = "10.1016/0020-0190(92)90226-L",

language = "English",

volume = "42",

pages = "299--302",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - On the equal-subset-sum problem

AU - Woeginger, G.J.

AU - Yu, Zhongliang

PY - 1992

Y1 - 1992

N2 - Given a set S of n integers, the problem is to decide whether there exist two disjoint nonempty subsets S1,S2S whose elements sum up to the same value. We show this problem to be NP-complete and we present an approximation algorithm with worst-case ratio 1.324 for the optimization version of this problem.

AB - Given a set S of n integers, the problem is to decide whether there exist two disjoint nonempty subsets S1,S2S whose elements sum up to the same value. We show this problem to be NP-complete and we present an approximation algorithm with worst-case ratio 1.324 for the optimization version of this problem.

U2 - 10.1016/0020-0190(92)90226-L

DO - 10.1016/0020-0190(92)90226-L

M3 - Article

SN - 0020-0190

VL - 42

SP - 299

EP - 302

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

On the equal-subset-sum problem

Abstract

Access to Document

Fingerprint

Cite this