License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.76
URN: urn:nbn:de:0030-drops-106527
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10652/
Go to the corresponding LIPIcs Volume Portal

Jin, Ce

An Improved FPTAS for 0-1 Knapsack

pdf-format:
LIPIcs-ICALP-2019-76.pdf (0.4 MB)

Abstract

The 0-1 knapsack problem is an important NP-hard problem that admits fully polynomial-time approximation schemes (FPTASs). Previously the fastest FPTAS by Chan (2018) with approximation factor 1+epsilon runs in O~(n + (1/epsilon)^{12/5}) time, where O~ hides polylogarithmic factors. In this paper we present an improved algorithm in O~(n+(1/epsilon)^{9/4}) time, with only a (1/epsilon)^{1/4} gap from the quadratic conditional lower bound based on (min,+)-convolution. Our improvement comes from a multi-level extension of Chan’s number-theoretic construction, and a greedy lemma that reduces unnecessary computation spent on cheap items.

BibTeX - Entry

@InProceedings{jin:LIPIcs.ICALP.2019.76,
  author =	{Jin, Ce},
  title =	{{An Improved FPTAS for 0-1 Knapsack}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{76:1--76:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/10652},
  URN =		{urn:nbn:de:0030-drops-106527},
  doi =		{10.4230/LIPIcs.ICALP.2019.76},
  annote =	{Keywords: approximation algorithms, knapsack, subset sum}
}

Keywords: approximation algorithms, knapsack, subset sum
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI