Maximizing minimum edge+node value in a directed graph

2
votes

I have a directed graph. Each edge has an intrinsic "weight" w_ij, which is fixed. Each node has a value v_i that can be configured, except for "root nodes" (no incoming edges) and "leaf nodes" (nooutgoing edges) whose values are fixed.

the "adjusted by node" edge value of each edge is given by: s_ij = w_ij + v_j - v_i that is, we adjust the the value of an edge by the difference of values of its adjacent nodes. Of course, changing the values of nodes will affect the values of s_ij.

I am interested in the value of min{s_ij}, and want to find the optimal assignment of values to nodes, so that this "bottleneck" value is maximized.

Any ideas of how to do that?

Note: Cycles and "fixed paths" from a root to a leaf provide upper bounds for the minimum value (e.g. in a cycle, the sum of node differences is always 0, so the best you could get is the average of the edges' intrinsic weights). But because cycles and "fixed paths" may overlap, it is not clear whether the minimal upper bound is attainable. It is likely that the solution will involve finding such paths/cycles first.

2
algorithmoptimizationgraphgraph-theorydirected-graph
Sounds like a classic flow question. Look into Edmonds-Karp and flow in general. I'd elaborate more but I'm on mobile. en.m.wikipedia.org/wiki/Flow_network - Benjamin Gruenbaum
Thanks. I initially thought of flow questions, but could not think of an intuitive reduction - I'll look at your suggestion. Just to give a bit of context, the question arises in scheduling/synchronization problems and the s_ij values are slack times or something similar - amit

2 Answers

4
votes

If I understand correctly, the problem can be formulated as this linear program. Adjust the input so that v_i = 0 for every vertex i that is a source or a sink.

maximize z

subject to
for every ij,
    z + v_i - v_j <= w_ij  (i.e., z <= w_ij + v_j - v_i = s_ij)

variables
z unbounded
for every vertex i not a source or sink,
    v_i unbounded

Here's the dual program.

minimize sum_ij of w_ij y_ij

subject to
sum_ij y_ij >= 1
for every vertex i not a source or sink,
    sum_j y_ij - sum_j y_ji = 0

variables
for every ij,
    y_ij >= 0

If we didn't exclude the sources and sinks from the conservation constraint, this would be exactly the linear program for minimum mean-cost cycle. As things stand, we still can use the flow decomposition technique to show that an optimum exists that is either a source-sink path or a cycle, and I believe that a slight modification of the simple algorithm for finding a minimum mean-cost cycle is applicable here.

Once you have the optimum value z*, you can find the potentials v_i by running Bellman-Ford with weights w_ij - z*. I apologize for not providing more details, but I have this nagging feeling that I'm doing your homework.

1
votes

I can think of two different approaches immediately:

First, you can binary search on the answer. Checking that you can attain a given minimum edge weight is very closely related to a shortest path problem --- you have a bunch of constraints on the differences of the node weights, and each constraint is of the form wi - wj >= lij with certain w's fixed.

Second, you could do subgradient optimisation. You want to maximise the minimum value of the edge weights. It's really easy to work out a subgradient here.

This problem probably has a lot of useful structure that I'm not exploiting here. You might try writing down a linear programming relaxation and playing with it some. Doing this --- analysing the problem more deeply --- will almost certainly lead to a faster algorithm than either approach outlined above.