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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

50 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	299-302
Tijdschrift	Information Processing Letters
Volume	42
Nummer van het tijdschrift	6
DOI's	https://doi.org/10.1016/0020-0190(92)90226-L
Status	Gepubliceerd - 1992

Toegang tot document

10.1016/0020-0190(92)90226-L

Citeer dit

@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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit