If you want to make money online : Register now

[Solved]: Is this problem NP-hard?

, , No Comments
Problem Detail: 

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!

Asked By : farseer

Answered By : Tom van der Zanden

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42978

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback