A fully polynomial approximation scheme for a knapsack problem with a minimum filling constraint (extended abstract)

Zhou Xu, Xiaofan Lai

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

Abstract

We study a variant of the knapsack problem, where a minimum filling constraint is imposed such that the total weight of selected items cannot be less than a given threshold. We consider the case when the ratio of the threshold to the capacity equals a given constant α with 0 ≤ α < 1. For any such constant α, since finding an optimal solution is NP-hard, we develop the first FPTAS for the problem, which has a time complexity polynomial in 1/(1 - α).
Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings
Pages704-715
Number of pages12
DOIs
Publication statusPublished - 1 Sep 2011
Event12th International Symposium on Algorithms and Data Structures, WADS 2011 - New York, NY, United States
Duration: 15 Aug 201117 Aug 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6844 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Symposium on Algorithms and Data Structures, WADS 2011
Country/TerritoryUnited States
CityNew York, NY
Period15/08/1117/08/11

Keywords

  • approximation algorithm
  • FPTAS
  • knapsack problem
  • minimum filling constraint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this