2
$\begingroup$

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).

The cost to send $x$ unit of flow through edge $e_i$ is defined as $w_i*F(x)$, where $w_i$ is the weight of edge $e_i$. Assume that the structure of graph $(V,E)$ is given, $F(X)$ is given, but $W$ is unknown.

If you were also given a series of (approximate or exact) minimum costs $C$ to send one unit of flow between each pair of neighbor nodes $(u,v)$, where there is a $e$ in $E$ that connects $u,v$.

How do I estimate the weights $W$ on the set of edges $E$?

And if the minimum costs are approximate, there might be inconsistency in this data, how do I estimate the approximate weights W to minimize the $L^2$ or $L^1$ norm?

Is there an efficient algorithm?

$\endgroup$
1
$\begingroup$

The minimum costs does not carry enough information to reconstruct the edge weights.

Counterexample: Three vertices a, b, b W(a,b) = W(a,c) = 1 < 2 << W(a,c)

The minimum cost from a to c is 2, and as long as W(a,c) is bigger than that, you can't recover it.

There could be some dynamic protocol where you can sent far more than unit flow.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.