2
$\begingroup$

Good day. Subset sum selection problem is NP-hard.

I trying to solve following problem: Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value. Solution: subset of size K, so that sum of all selected items and items within radius(when selected items is in center) is maximal.

Here example(with radius 1 and K=2): Example

On this picture 2 orange items selected. all blue and green items are added to sum also, but green item, added only once( in other words any item on grid can be taken once in final sum).

So sum of selected subse: 2xOrange(selected)+9xBlue(adjacent)+1xGreen(taken only once into account).

When radius is 0 the problem is trivial: Just choose K best items, But when radius 1 or more is following problem NP-hard?

If yes, what is the best way to prove it ?

If no, is there an algorithm that return optimal solution?

Many thanks for help!

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ What have you tried and where did you get stuck? Is $R$ fixed or part of the input? $\endgroup$ – Raphael♦ May 27 '15 at 6:39
  • 1
    $\begingroup$ R is part of the input. I tried to find polynomial algorithm , but failed. Now trying to find good reduction to NP-hard problem. $\endgroup$ – farseer May 28 '15 at 7:19
2
$\begingroup$

It seems very likely that it is $NP$-complete.

A good "trick" to tackle a problem like this would be to create an instance where there are $X$ very big numbers in the grid and you're allowed to choose $X$ items. Choose the goal amount so that you need all of these big numbers, and this constrains you to "use" all of the $X$ items to cover the $X$ big numbers. The only freedom is in where exactly you pick the position of the rectangles relative to the big numbers.

A good candidate for a reduction would be Vertex Cover, which is $NP$-complete even for planar, 3-regular graphs. You could fix some embedding of the graph in the plane, and then place large numbers on the edges, so that you need to collect these numbers to win. You'd make $K$ so large that you can cover almost all of the big numbers in each edge, but not quite. Placing a rectangle at the position of a vertex would cover numbers in all of the incident edges.

I'll leave it to you to figure out the details (since you only asked for a "way" to prove it) but I'm pretty sure this is a feasible approach.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Thanks for answer. Perhaps you can give small example of reduction ? Also, what you think about same problem, but 1-dimensional? If this problem is also NP-hard, 2-dimensional is NP-hard for sure. $\endgroup$ – farseer May 28 '15 at 9:04
  • 2
    $\begingroup$ The 1D case is polynomially solvable using dynamic programming. If all values are positive then it's very easy (since it never makes sense to have rectangles overlap) but in either case it's possible. It's a proof sketch, but working out all the nitty-gritty details would be quite annoying/time consuming. I'm not sure if it's even correct, but it seems like a decent starting point if someone else would want to actually work it out. You'll have to excuse me for being lazy ;-) $\endgroup$ – Tom van der Zanden May 28 '15 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.