0
$\begingroup$

In many NP-hard problem there is a budget constraint. Each element $e$ in the instance has a certain cost $c(e)$ and a profit $p(e)$; a feasible solution $S$ for the considered problem cannot exceed the budget constraint, i.e., $\sum_{e \in S} c(e) \leq K$, for some fixed budget $K$, and the goal is to maximize the total profit $\sum_{e \in S} p(e)$. An example for such a problem is the knapsack problem (i.e., without any other constraints). However, the knapsack problem is no longer NP-Hard for polynomially bounded profits/costs.

Question: Is there an NP-Hard problem with a single budget constraint and polynomially bounded profits (and arbitrary costs), that becomes polynomially solvable if the costs are also polynomially bounded?

In other words, I am interested in a weakly-NP-Hard variation of the $0/1$-knapsack problem with added constraints for which the non polynomial numbers in the instance are the costs (and not the profits). Note that the knapsack problem itself does not answer my question since it is not NP-Hard for polynomially bounded profits (even for arbitrary costs).

Improve this question
$\endgroup$
7
  • $\begingroup$ What other budget constraint problems are you thinking of? It seems to me that the standard polytime solution to the knapsack problem would also solve any similar problem with a polytime reward function. And other NP-hard problems like BSAT or Vertex Cover don't really seem to fit in to this schema. $\endgroup$
    – Holden Rohrer
    May 6 at 16:56
  • $\begingroup$ If I could give you an example I would be answering my own question:) Note that there are other variants of knapsack, e.g., multi-dimentional knapsack or multiple-choice knapsack, for which the classic pseudo-polynomial for knapsack cannot be used. $\endgroup$
    – John
    May 6 at 17:42
  • $\begingroup$ en.m.wikipedia.org/wiki/Strong_NP-completeness $\endgroup$
    – Lamine
    May 6 at 21:46
  • $\begingroup$ @Lamine Unfortunately Strong-NP-Hard problems do not fulfill the requirements above: in such problems, even if the costs are polynomial the problem remains NP-Hard. I want the problem to be polynomially solvable for polynomial costs. $\endgroup$
    – John
    May 7 at 3:51
  • $\begingroup$ Subset Sum is the underlying NP-Complete decision problem for Knapsack. You can look up the Multiple Knapsack problem with 2 bins. Even with unit profits the problem is NP-Hard and also does not admit an FPTAS. But it is poly-time solvable if item sizes are poly-bounded. Similarly multi-dimensional knapsack with 2 dimensions. $\endgroup$
    – Chandra Chekuri
    May 7 at 4:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.