Lecture19_ShortestPaths3
Tuesday, October 20, 2020
9:20 PM
Linear Programming
Let A be an m×n matrix, b be an m-vector, and c be an n-vector. Find an n-vector x that maximizes cTx subject to Ax <= b, or determine that no such solution exists.
Algorithms for the general problem
• Simplex methods —practical, but worst-case exponential time.
• Interior-point methods —polynomial time and competes with simplex.
Feasibility problem: No optimization criterion. Just find x such that Ax <= b.
• In general, just as hard as ordinary LP.
Solving a system of difference constraints
Linear programming where each row of A contains exactly one 1, one –1, and the rest 0's.
• For each unknown crate a vertex.
• For each inequality / constrain put an edge from the one with negative sign to the one
with positive sign. The weight of edge will be the right hand side of the inequality.
Unsatisfiable constraints
Theorem. If the constraint graph contains a negative-weight cycle, then the system of differences is unsatisfiable.
• Right side: negative number -> contradiction
Satisfying the constraints
Theorem. Suppose no negative-weight cycle exists in the constraint graph. Then, the constraints are satisfiable.
• s: dummy variable, a vertex that connect to all vertices.
Analysis of Algorithms Page 1
Bellman-Ford and linear programming
Corollary. The Bellman-Ford algorithm can solve a system of m difference constraints on n variables in O(mn) time.
Application to VLSI layout compaction
• Subject to the second optimalization function above
Analysis of Algorithms Page 2