Maximum WPD for a collection of placement locations

[cmccoy]

Compute the maximum WPD for a collection of placement locations

Define

Let P = the set of placements on the tree

Let I = the points that form the convex hull of P

Let p_i = the proportion of total mass at point i

Let E = the set of edges connecting I

Let D_e = the subset of I distal to edge e

Let x_e = 1 - 2\sum_{i \in D_e} p_i, for edge e, so |x_e| is one minus the proportion of mass on the side with least mass.

Let l_e = length of edge e

We want to minimize:

z = \sum_e l_e |x_e|

Subject to:

• p_i \ge 0 (no negative mass)
• \sum_i p_i = 1 (mass proportions sum to 1)

  Linear Conversion

To convert this to a linear program, replace:

• x_e = xp_e - xn_e
• |x_e| = xp_e + xn_e

subject to xp_e,xn_e >= 0 (see AIIMS linear programming tricks)

The problem becomes:

Minimize:

z = \sum_e l_e (xp_e + xn_e)

Subject to:

• p_i >= 0 for all i (no negative mass)
• \sum_{i \in i} p_i = 1 (mass proportions sum to 1)
• 1 - 2\sum_{i \in D_e} p_i = xp_e - xn_e for all e
• xp_e,xn_e >= 0 for all e

[matsen]

This one was my mistake and we have moved onto greener pastures.