A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

Research output: Journal article publicationJournal articleAcademic researchpeer-review

15 Citations (Scopus)

Abstract

The symmetric quadratic knapsack problem (SQKP), which has several applications in machine scheduling, is NP-hard. An approximation scheme for this problem is known to achieve an approximation ratio of (1 + ) for any > 0. To ensure a polynomial time complexity, this approximation scheme needs an input of a lower bound and an upper bound on the optimal objective value, and requires the ratio of the bounds to be bounded by a polynomial in the size of the problem instance. However, such bounds are not mentioned in any previous literature. In this paper, we present the first such bounds and develop a polynomial time algorithm to compute them. The bounds are applied, so that we have obtained for problem (SQKP) a fully polynomial time approximation scheme (FPTAS) that is also strongly polynomial time, in the sense that the running time is bounded by a polynomial only in the number of integers in the problem instance.
Original languageEnglish
Pages (from-to)377-381
Number of pages5
JournalEuropean Journal of Operational Research
Volume218
Issue number2
DOIs
Publication statusPublished - 16 Apr 2012

Keywords

  • Combinatorial optimization
  • FPTAS
  • Machine scheduling
  • Quadratic knapsack
  • Strongly polynomial time

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Modelling and Simulation
  • Information Systems and Management

Cite this