On strong NP-completeness of rational problems

DOI10.1007/978-3-319-90530-3_26MaRDI QIDQ1625182zbMATH OpenOpenAlexFDO

Authors Dominik Wojtczak

Publication date 28 November 2018

Full work available at URL https://arxiv.org/abs/1802.09465

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

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.

Recommendations

• NP-completeness notions under strong hypotheses
• Separating NP-completeness notions under strong hypotheses
• A note on non-complete problems in \(NP_\mathbb{R}\)
• NP-completeness results for deductive problems on stratified terms
• scientific article; zbMATH DE number 3921977
• Optimization and \(\mathrm{NP}_{\mathbb{R}}\)-completeness of certain fewnomials
• Autoreducibility of NP-complete sets under strong hypotheses
• Decidability of NP-complete problems
• On Some $\mathcal{NP}$ -complete SEFE Problems
• On the Strong Parrott Completion Problem

Cited in

(11)

• NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times
• Rikudo is NP-complete
• Positive planar satisfiability problems under 3-connectivity constraints
• On the complexity of variations of equal sum subsets
• scientific article; zbMATH DE number 7599997 (Why is no real title available?)
• Coordination games on weighted directed graphs
• Approximating single- and multi-objective nonlinear sum and product knapsack problems
• Simple approximations for general spanner problems
• The two-squirrel problem and its relatives
• The complexity of linear temporal verification for continuous counter systems
• Overcoming poor data quality: optimizing validation of precedence relation data

This page was built for publication: On strong NP-completeness of rational problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1625182)