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 language | English |
---|---|
Pages (from-to) | 377-381 |
Number of pages | 5 |
Journal | European Journal of Operational Research |
Volume | 218 |
Issue number | 2 |
DOIs | |
Publication status | Published - 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