Solving a system of difference constraints Linear programming where each row of A contains exactly one l, one-l, and the rest os Example: Solution: x1-x2≤3 x1=3 2-x3≤-2 X x:-x:<1 2=0 x1-x3≤2 2 Constraint graph: (The"A matrix has W x:-X;<1 dimensions E×|) c 2001 by Charles E Leiserson Introduction to Agorithms Day31L18.19© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.19 Solving a system of difference constraints Linear programming where each row of A contains exactly one 1, one –1, and the rest 0’s. Example: x1 – x2 ≤ 3 x2 – x3 ≤ –2 x1 – x3 ≤ 2 xj – xi ≤ wij Solution: x1 = 3 x2 = 0 x3 = 2 Constraint graph: vj v v j i vi xj – xi ≤ wij wij (The “A” matrix has dimensions |E| × |V|.)