<p>In many NP-hard problem there is a <em>budget</em> constraint. Each element <span class="math-container">$e$</span> in the instance has a certain cost <span class="math-container">$c(e)$</span> and a profit <span class="math-container">$p(e)$</span>; a feasible solution <span class="math-container">$S$</span> for the considered problem cannot exceed the budget constraint, i.e., <span class="math-container">$\sum_{e \in S} c(e) \leq K$</span>, for some fixed budget <span class="math-container">$K$</span>, and the goal is to maximize the total profit <span class="math-container">$\sum_{e \in S} p(e)$</span>. 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.</p>
<p><strong>Question:</strong> 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?</p>
<p>In other words, I am interested in a <strong>weakly-NP-Hard</strong> variation of the <span class="math-container">$0/1$</span>-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).</p>

CC BY-SA 4.0
2023-05-06T16:56:50.603Z
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.
Holden Rohrer
CC BY-SA 4.0
2023-05-06T17:42:00.233Z
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.
John
CC BY-SA 4.0
2023-05-06T21:46:34.987Z
https://en.m.wikipedia.org/wiki/Strong_NP-completeness
Lamine
CC BY-SA 4.0
2023-05-07T03:51:05.533Z
@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.
John
CC BY-SA 4.0
2023-05-07T04:28:44.493Z
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.
Chandra Chekuri
CC BY-SA 4.0
2023-05-07T05:43:59.393Z
@ChandraChekuri Thanks these are good examples:) however, I am interested in problems where there is a single budget constraint. The problems you refer to are with multiple budgets (in two different ways). I will update my post to clarify.
John
CC BY-SA 4.0
2023-05-07T18:31:14.133Z
What does it mean to have a single budget constraint? What is the restriction on the other constraints? Can one ask for a matroid constraint which is purely combinatorial and does not have any numbers? Or some other independence constraint? What you are asking for is not formal enough.
Chandra Chekuri
<np-hardness><approximation-algorithms><approximation-hardness><polynomials><packing>
When Exponential Costs are Essential for NP-Hardness?
John
# When Exponential Costs are Essential for NP-Hardness?

(Asked by: username_0 on 2023-05-06)

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).

**Tags:** np-hardness, approximation-algorithms, approximation-hardness, polynomials, packing

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: https://en.m.wikipedia.org/wiki/Strong_NP-completeness  
> **username_0**: @username_2 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.  
> **username_3**: 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.  
> **username_0**: @ChandraChekuri Thanks these are good examples:) however, I am interested in problems where there is a single budget constraint. The problems you refer to are with multiple budgets (in two different ways). I will update my post to clarify.  
> **username_3**: What does it mean to have a single budget constraint? What is the restriction on the other constraints? Can one ask for a matroid constraint which is purely combinatorial and does not have any numbers? Or some other independence constraint? What you are asking for is not formal enough.  

---

## 0 answers

