On Strong NP-Completeness of Rational Problems

Wojtczak, Dominik ORCID: 0000-0001-5560-0546 (2018) On Strong NP-Completeness of Rational Problems. In: International Computer Science Symposium in Russia.

	Text csr18.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (195kB)
	Text csr18.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (195kB)

Abstract

The computational complexity of the partition, 0-1 subset sum, unbounded subset sum, 0-1 knapsack and unbounded knapsack problems and their multiple variants were studied in numerous papers in the past where all the weights and profits were assumed to be integers. We re-examine here the computational complexity of all these problems in the setting where the weights and profits are allowed to be any rational numbers. We show that all of these problems in this setting become strongly NP-complete and, as a result, no pseudo-polynomial algorithm can exist for solving them unless P = NP. Despite this result we show that they all still admit a fully polynomial-time approximation scheme.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	23 Oct 2019 13:22
Last Modified:	19 Jan 2023 00:28
DOI:	10.1007/978-3-319-90530-3_26
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3052214

Available Versions of this Item

• On Strong NP-Completeness of Rational Problems. (deposited 31 May 2018 10:03)
  • On Strong NP-Completeness of Rational Problems. (deposited 23 Oct 2019 13:22) [Currently Displayed]