On local search for weighted k-set packing

Esther M. Arkin; Refael Hassin

doi:10.1007/3-540-63397-9_2

On local search for weighted k-set packing

Esther M. Arkin
, Refael Hassin

Applied Mathematics and Statistics

Tel Aviv University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

21 Scopus citations

Abstract

Given a collection of sets of cardinality at most k, with weights for each set, the maximum weighted packing problem is that of finding a collection of disjoint sets of maximum total weight. We study the worst case behavior of the t-local search heuristic for this problem proving a tight bound of k - 1 + 1/t. This continues the work of Hurkens and Schrijver for unweighted packing problems.

Original language	English
Title of host publication	Algorithms - ESA 1997 - 5th Annual European Symposium, Proceedings
Editors	Rainer Burkard, Gerhard Woeginger
Publisher	Springer Verlag
Pages	13-22
Number of pages	10
ISBN (Print)	3540633979, 9783540633976
DOIs	https://doi.org/10.1007/3-540-63397-9_2
State	Published - 1997
Event	5th Annual European Symposium on Algorithms, ESA 1997 - Graz, Austria Duration: Sep 15 1997 → Sep 17 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1284
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th Annual European Symposium on Algorithms, ESA 1997
Country/Territory	Austria
City	Graz
Period	09/15/97 → 09/17/97

Access to Document

10.1007/3-540-63397-9_2

Cite this

Arkin, E. M., & Hassin, R. (1997). On local search for weighted k-set packing. In R. Burkard, & G. Woeginger (Eds.), Algorithms - ESA 1997 - 5th Annual European Symposium, Proceedings (pp. 13-22). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1284). Springer Verlag. https://doi.org/10.1007/3-540-63397-9_2

@inproceedings{69a1f1a4347844b0a467937855dde4b5,

title = "On local search for weighted k-set packing",

abstract = "Given a collection of sets of cardinality at most k, with weights for each set, the maximum weighted packing problem is that of finding a collection of disjoint sets of maximum total weight. We study the worst case behavior of the t-local search heuristic for this problem proving a tight bound of k - 1 + 1/t. This continues the work of Hurkens and Schrijver for unweighted packing problems.",

author = "Arkin, \{Esther M.\} and Refael Hassin",

year = "1997",

doi = "10.1007/3-540-63397-9\_2",

language = "English",

isbn = "3540633979",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "13--22",

editor = "Rainer Burkard and Gerhard Woeginger",

booktitle = "Algorithms - ESA 1997 - 5th Annual European Symposium, Proceedings",

}

Arkin, EM & Hassin, R 1997, On local search for weighted k-set packing. in R Burkard & G Woeginger (eds), Algorithms - ESA 1997 - 5th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1284, Springer Verlag, pp. 13-22, 5th Annual European Symposium on Algorithms, ESA 1997, Graz, Austria, 09/15/97. https://doi.org/10.1007/3-540-63397-9_2

On local search for weighted k-set packing. / Arkin, Esther M.; Hassin, Refael.
Algorithms - ESA 1997 - 5th Annual European Symposium, Proceedings. ed. / Rainer Burkard; Gerhard Woeginger. Springer Verlag, 1997. p. 13-22 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1284).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On local search for weighted k-set packing

AU - Arkin, Esther M.

AU - Hassin, Refael

PY - 1997

Y1 - 1997

N2 - Given a collection of sets of cardinality at most k, with weights for each set, the maximum weighted packing problem is that of finding a collection of disjoint sets of maximum total weight. We study the worst case behavior of the t-local search heuristic for this problem proving a tight bound of k - 1 + 1/t. This continues the work of Hurkens and Schrijver for unweighted packing problems.

AB - Given a collection of sets of cardinality at most k, with weights for each set, the maximum weighted packing problem is that of finding a collection of disjoint sets of maximum total weight. We study the worst case behavior of the t-local search heuristic for this problem proving a tight bound of k - 1 + 1/t. This continues the work of Hurkens and Schrijver for unweighted packing problems.

UR - https://www.scopus.com/pages/publications/84949202284

U2 - 10.1007/3-540-63397-9_2

DO - 10.1007/3-540-63397-9_2

M3 - Conference contribution

AN - SCOPUS:84949202284

SN - 3540633979

SN - 9783540633976

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 22

BT - Algorithms - ESA 1997 - 5th Annual European Symposium, Proceedings

A2 - Burkard, Rainer

A2 - Woeginger, Gerhard

PB - Springer Verlag

T2 - 5th Annual European Symposium on Algorithms, ESA 1997

Y2 - 15 September 1997 through 17 September 1997

ER -

On local search for weighted k-set packing

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this