Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I would like to know whether the following problem, including algorithms to solve it (exact or approximations) has been studied.

A finite set of positive-weighted points are given in the n-dimensional Euclidean space. Find the tree (extra points, that is Steiner points, are allowed) that connects all given points and minimizes the sum of the weighted lengths: Given such a tree, each edge partitions the set of (original) points into two groups (call them "left" and "right"). The weight of the edge is defined to be

$w_e=\sqrt(\sum_{left}weights\cdot\sum_{right}weights)$

So we need to minimize

$\sum_{e\in E} l_ew_e$

where $l_e$ is the length of the edge (notice that edges and their weights depend on the chosen connectivity/topology).

One can imagine this problem as minimizing the cost of building a road network that connects a set of given points=cities, where each section of the road needs a width (so not only the length matter, but the total "area" of material needed) that is proportional to the traffic, which in turns is higher the more that section of the road divides the total population into two equally numerous sets.

share|improve this question
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.