6
$\begingroup$

I am trying to solve a system of inequalities in the following form: $\ x_i - x_j \leq w $

I know these inequalities can be solved using Bellman-Ford algorithm. But there is also another condition. I want to find the solution that maximizes $\ x_n - x_1$

As far as I know the default Bellman-Ford algorithm minimizes it. How do I do that?

$\endgroup$

migrated from cstheory.stackexchange.com Apr 20 '13 at 21:52

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ Bellman-Ford is a graph algorithm; how do you translate a set of inequalities into a graph? Look at that and you may find which other graph problem corresponds to your. $\endgroup$ – Raphael Aug 26 '13 at 11:06
3
$\begingroup$

The textbook Bellman-Ford algorithm will indeed minimize the span of the variables: $max_i(x_i) - min_i(x_i)$. It involves adding a supernode and 0-weight edges from the supernode to every other nodes in the graph. This is probably what the op is referring to.

To maximize $x_n - x_1$, as usual, convert the difference constraints to edges. However, we will not add the super node and its 0 weight edges. Instead, just run Bellman-Ford using the node for $x_1$ as source:

  1. If negative cycle is detected, the constraints can't be satisfied.
  2. The result distance $x_n$ will maximize $x_n - x_1$. If $x_n$ is infinity, that means $x_1$ and $x_n$ can be arbitrarily far apart.

Now let's see why it works.

Why do the $x$s satisfy the constraints?
Proof: By triangle inequality, same as the textbook Bellman-Ford method. I won't repeat it here.

Why will the result distance $x_n$ maximize $x_n - x_1$?
Proof: Consider the shortest path $p = (v_1, v_2,...,v_n)$ from $v_1$ to $v_n$, the path corresponds to the following set of constraints:

      $x_2-x_1\leq w[1,2]$
      $x_3-x_2\leq w[2,3]$
            ...
      $x_n-x_{n-1}\leq w[n-1,n]$

Summing the constraints, we obtain:

      $x_n-x_1\leq\sum_2^n w[i-1,i]=w(p)$

That is, in any solution that satisfies the constraints, $x_n - x_1$ cannot be greater than $w(p)$, the weight of the shortest path from $v_1$ to $v_n$. As Bellman-Ford sets $x_n-x_1$ to the shortest path value, this implies $x_n-x_1$ is as large as possible.

$\endgroup$
0
$\begingroup$

Your can model this problem as a graph problem: The vertices are called $v_i$ (one $v_i$ for every $x_i$) and you have a directed edge $(v_i,v_j)$ with weight $w$ for every constraint $x_j - x_i \le w$.

First note that for some feasible solution you can add an offset for all $x_i$ and get another solution which is equally good. So you can assume that $x_1=0$. If you have a directed cycle in the graph, you problem becomes unfeasible - so you check this first. What you do next is to perform a single-source shortest path query for $v_1$, then you set $x_j:=d(v_1,v_j)$.

Why does this work? Assume that there is directed edge $(v_a,v_b)$, and assume $d(v_1,v_a)>d(v_1,v_b)$. The you have $d(v_1,v_a) + d(v_a,v_b) \ge d(v_1,v_b)$, which gives $$d(v_a,v_b)=w \ge d(v_1,v_b) -d(v_1,v_a) = x_b - x_a.$$

Obviously, there is no better solution because you have a "chain of constraints", connecting $v_1$ with $v_n$, and if you would increase $x_n$ one of these constraints would be violated.

Notice that all the weights are the same the is no need to execute the Bellman-Ford algorithm. You can do a Breadth-First-Search instead which has the better running time.

$\endgroup$
  • $\begingroup$ Are you assuming the weight $w$ is the same for all constraints? I didn't read the question that way; I think $w$ might be different for every constraint. Consequently, I don't think BFS is going to suffice. $\endgroup$ – D.W. Aug 26 '13 at 18:15
0
$\begingroup$

Maximizing $x_n-x_1$ is equivalent to minimizing $x_1-x_n$. So, if there's a way to use Bellman-Ford to minimize $x_1-x_n$, you're done. I don't know whether Bellman-Ford will do that.

Alternatively: Another approach would be to use binary search to find the largest number $D$ such that $x_n - x_1 \le D$ is consistent with the rest of your system of inequalities. You can use Bellman-Ford to test whether your system, plus the constraint $x_n - x_1 \le D_i$ (for a particular constant number $D_i$), is feasible, and that tells you whether you should increase $D$ or decrease $D$. Use binary search, and with logarithmically many executions of Bellman-Ford, you'll find this $D$ -- and that's the answer to your original problem.

$\endgroup$
5
$\begingroup$

The obvious (but perhaps not optimal) solution would be to give it as input to a LP solver.

$\endgroup$

Your Answer

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