New answers tagged np-hard
0
votes
NP-hardness of modified distance-colouring of graphs
The problem you describe (for $r=1$) falls under the so-called $[\sigma,\rho]$-partitioning framework with several hardness results available (see e.g., [1]). In such a problem, we want to color the ...
- 22.5k
0
votes
NP-hardness of modified distance-colouring of graphs
I don't have an answer to your problem, but I have an answer for a different problem.
Let the Annotated Colorful Neighborhood-problem be as follows.
Annotated 2-Colorful 1-Neighborhood
Input: $G = (V, ...
- 15.5k
1
vote
Accepted
Fully Connected Graph to Lattice
Your problem is NP-Hard.
Consider the variant of the problem in which you need to delete the edges of a complete graph with $n$ vertices in order to obtain a $1 \times n$ lattice of minimum weight.
...
- 28.2k
2
votes
Accepted
What is the complexity of minimising a convex quadratic function over the integers?
The closest lattice vector problem is NP-hard in the $L_2$ norm. See NP completeness of closest vector problem for a reference to the proof.
D.W.♦
- 156k
0
votes
Subset sum reducible to barter economy problem?
You can reduce from subset-sum as follows: given a set of $n$ positive integers $x_1, \dots, x_n$ and a positive integer target $T$, consider an instance with $2$ people $p_1, p_n$ and $n+1$ objects $...
- 28.2k
0
votes
Accepted
Is there an efficient algorithm for this ecommerce optimization problem?
The usual rule on this site is to ask only one question per post, so I'll answer the first question. Specifically, I'll focus on the case where there is only one discount rule, and it can only be ...
D.W.♦
- 156k
Top 50 recent answers are included