New answers tagged

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 ...
Juho's user avatar
  • 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, ...
Pål GD's user avatar
  • 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. ...
Steven's user avatar
  • 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.'s user avatar
  • 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 $...
Steven's user avatar
  • 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.'s user avatar
  • 156k

Top 50 recent answers are included