Ward, Justin and Sviridenko, Maxim (2013) Large neighborhood local search for the maximum set packing problem. In: Freĭvalds, R. V. and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , D. (David), (eds.) Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I. Lecture Notes in Computer Science (7965). Berlin ; London: Springer, pp. 792-803. ISBN 9783642392054

Preview

PDF WRAP_1271053-cs-091214-icalp13-postprint.pdf - Accepted Version - Requires a PDF viewer. Download (528Kb) | Preview

Request Changes to record.

Abstract

In this paper we consider the classical maximum set packing problem where set cardinality is upper bounded by a constant k. We show how to design a variant of a polynomial-time local search algorithm with performance guarantee (k + 2)/3. This local search algorithm is a special case of a more general procedure that allows to swap up to Θ(logn) elements per iteration. We also design problem instances with locality gap k/3 even for a wide class of exponential time local search procedures, which can swap up to cn elements for a constant c. This shows that our analysis of this class of algorithms is almost tight.

Item Type:	Book Item
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Approximation algorithms, Linear programming
Series Name:	Lecture Notes in Computer Science
Publisher:	Springer
Place of Publication:	Berlin ; London
ISBN:	9783642392054
ISSN:	0302-9743
Book Title:	Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I
Editor:	Freĭvalds, R. V. and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , D. (David)
Official Date:	2013
Dates:	Date Event 2013 Published
Number:	7965
Page Range:	pp. 792-803
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Description:
Date of first compliant deposit:	28 July 2016
Date of first compliant Open Access:	28 July 2016
Funder:	Engineering and Physical Sciences Research Council (EPSRC), Seventh Framework Programme (European Commission) (FP7), Royal Society (Great Britain)
Grant number:	EP/J021814/1 (EPSRC), EP/D063191/1 (EPSRC)
Title of Event:	40th International Colloquium on Automata, Languages, and Programming, ICALP 2013
Type of Event:	Other
Location of Event:	Riga, Latvia
Date(s) of Event:	8-12 July 2013

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads