On Strong NP-Completeness of Rational Problems
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.
Code (0)
등록된 구현이 없습니다.
Tasks
AllSimilar Papers 제목 키워드 기반
Coherence without Rationality at the Zero Lower Bound
Standard rational expectations models with an occasionally binding zero lower bound constraint either admit no solutions (incoherence) or multiple solutions (incompleteness). This paper shows that deviations from full-in…
FrictionWhen Input Integers are Given in the Unary Numeral Representation
Many NP-complete problems take integers as part of their input instances. These input integers are generally binarized, that is, provided in the form of the "binary" numeral representation, and the lengths of such binary…
BinarizationDifferentially Private Multi-Agent Planning for Logistic-like Problems
Planning is one of the main approaches used to improve agents' working efficiency by making plans beforehand. However, during planning, agents face the risk of having their private information leaked. This paper proposes…
Privacy PreservingCompleteness and Performance Of The APO Algorithm
Asynchronous Partial Overlay (APO) is a search algorithm that uses cooperative mediation to solve Distributed Constraint Satisfaction Problems (DisCSPs). The algorithm partitions the search into different subproblems of …
Unbalanced Incomplete Multi-view Clustering via the Scheme of View Evolution: Weak Views are Meat; Strong Views do Eat
Incomplete multi-view clustering is an important technique to deal with real-world incomplete multi-view data. Previous works assume that all views have the same incompleteness, i.e., balanced incompleteness. However, di…
ClusteringIncomplete multi-view clusteringMulti-view Subspace Clustering