MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.