Optimization problem in connected graphs with profits

Question

I am trying to develop an algorithm to solve a problem that I am not able to classify, I expose the subject:

You have a map divided into sections that have a certain area and where a certain number of people live.

The problem consists of finding sets of connected sections whose area does not exceed a certain value maximizing the number of selected inhabitants.

For now I can think of two approaches:

• Treat the problem as an all-pairs shortest paths problem in an undirected graph with positive natural values where the solutions that do not meet the constraint of the maximum selected area will be discarded. For this you could use the Floyd-Warshall algorithm, Dijkstra for all pairs or Thorup algorithm (which can be done in time V * E, where these are the vertices and edges of the graph).
• Treat it as an open vehicle routing problem with profits where each vehicle can start and end wherever it wants (open vehicle routing problem with profits or OVRPP).
• Another aproach

Also, depending on the combinatorics of the particular problem it is possible in certain cases to use genetic algorithms, together with tabu search, but this is only for cases where finding an optimal solution is inadmissible.

To be clearer, what is sought is to obtain a selection of connected sections whose sum of areas does not exceed a total area. The parameter to maximize is the sum of populations of the selected sections. The objective is to find an optimal solution.

For example, this is the optimal selection with max area of 6 (red color area)

Thank you all in advance!

Answer 1

Originally was going to leave this as a comment, as it doesn't constitute a complete answer with coded solution, but I believe it may approximate the canonical one.

Your problem has been studied extensively (perhaps not this particular variation, but many others including this one.) It is a variant of the knapsack problem and is NP-complete or harder (NP-hard). This should be obvious since a special case of your problem is when all nodes are connected to all other nodes, which is precisely the 0-1 knapsack problem.

In reference (1), the authors show an approximation algorithm that approximates with lower and upper bounds of

(1−ε)/2 ·(1 − 1/e^(1−ε))

and

1 − 1/e + ε

respectively, which is probably as close as you will get in terms of a good approximation algorithm.

There is a simple variation of the dynamic programming solution to the 0-1 knapsack problem that would yield a good approximation, which I can discuss some more if there is interest and time.

(1) Borradaile, Glencora, Brent Heeringa, and Gordon Wilfong. "The knapsack problem with neighbour constraints." Journal of Discrete Algorithms 16 (2012): 224-235.