2
$\begingroup$

I have the following problem:

Inputs:

  • A finite collection $V$ of vertices
  • A metric cost function $c:V^2\to\Bbb R$ (interpreted as the edge cost of a complete graph on $V$)
  • An amount of resource $s:V\to\Bbb R$ on each vertex, satisfying $\sum_{u\in V}s(u)=0$

The problem is to determine a transfer function $f:V^2\to\Bbb R^{\ge0}$ such that $\sum_{v\in V}(f(v,u)-f(u,v))=s(u)$ for all $u$, which minimizes $\sum_{u,v}f(u,v)c(u,v)$.

The story to tell is that the points represent places with some amount of resource (if $s(u)$ is positive) or with some need of the resource (if $s(u)$ is negative), and $c(u,v)$ is the cost of sending a unit of resource from $u$ to $v$. We assume that every vertex can send resource to any other vertex, and the direct path is usually better than passing through an intermediate point. How do we minimize the cost of sending everything from where it is to where it is needed?

What is the name of this problem, and do there exist efficient algorithms to solve it? It seems similar to the minimum cost flow problem, but this only has one source and one sink, has maximum capacities for all the edges, and often needs multiple node paths for the resource, while here the direct path is always at least as good as a longer path (because the cost function is a metric).

$\endgroup$
2
$\begingroup$

This is an instance of the minimum-cost circulation problem. Replace each vertex $v$ by two vertices $v_\text{in}$,$v_\text{out}$. Each edge $(u,v)$ is replaced by $(u_\text{out},v_\text{in})$, with capacity (upper bound) given by $c(u,v)$ and lower bound 0. Then, add an edge $(v_\text{in},v_\text{out})$ with both the lower bound and upper bound set to $s(v)$.

There are polynomial-time algorithms for this problem.

$\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.