Solutions and Approximations in Linear Programming
Explore exact solutions and approximations in linear programming through discussions on finding corners, minimum cost perfect matching in bipartite graphs, vertex cover, integer programming, LP for vertex cover, and matching. Learn about theorems, constraints, unique solutions, vertices, edges, and optimizations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Finding corners Two half planes with equality give a corner
Minimum cost Perfect Matching In Bipartite Graphs We discuss an LP of the form Maximize AX Subject to Ax b x 0
Theorem The constraints x 0 imply that there are more constraints than variables. Theorem: a corner is derived by taking an independent collection of constraints. Their size should be equal to the number of variables. Set an equality and solve A x =b
Theorem Since the rows are independent A x =b has a unique solution, which is a BFS
Vertex cover A set of S of vertices so that for every edge (v,u) u S or v S. 1 2 3 5 4 6 7
Vertex cover The vertices marked green are a vertex cover 1 2 3 5 4 6 7
Vertex cover The vertices marked green are a vertex cover 1 2 3 5 4 6 7
IP for vertex cover A variable xv for every v which is 1 if v is chosen and 0 otherwise. The IP is Minimize v xv Subject To xv+xu 1 for every e=(u,v) xv {0,1} for all v.
LP for vertex cover A variable xv for every v which is 1 if v is chosen and 0 otherwise. The IP is Minimize v xv Subject To xv+xu 1 for every e=(u,v) xv 0 for all v.
LP for vertex cover The LP gives smaller values than the IP 1/2 1/2 1/2
Matching A collection of edges who don t share a vertex 1 2 3 5 4 6 7
Matching A matching of size 2 1 2 3 5 4 6 7
Matching Claim: Let vc* be the minimum size vertex matching an mm* be the maximum size matching. Then vc* mm* 1 2 3 5 4 6 7
Matching Proof: Every edge in the matching required a different vertex 1 2 3 5 4 6 7
Matching Remark: For a triangle, a vertex cover has size 2 and a matching has size 1. 1 2 3 5 4 6 7
Matching The minimum size vertex cover problem is NPC. But the maximum matching problem is polynomial. 1 2 3 5 4 6 7
An independent set S An independent set S is a collection of vertices no two of which are neighbors. 1 2 3 5 4 6 7
Independent Set The vertices marked red are an independent set 1 2 3 5 4 6 7
An IP for independent set A variable xv that is 1 if xv is in the set and 0 otherwise Maximize v xv Subject to xv+xu 1 for every e=(u,v) xv 0 for every v
The LP is meaningless Assume that all edges are in the graph This means that the maximum independent set has size 1. But the fractional independent set has size n/2. Give every vertex value .
Coloring Minimum coloring: Assign colors to the vertices of the graph so that Neighbors get different colors, and minimize the number of colors used 1 2 3 5 4 6 7
Graphs Minimum coloring: A coloring of the graph with 3 colors. 1 2 3 5 4 6 7
Example A coloring of a graph is an assignment of colors to the vertices so that no two neighbors are assigned the same color. Example: The problem of checking if a graph is 2-colorable is in P.
Algorithm Distance i+1 are neighbors of distance i that have distance larger than i. D=0 D=1 D=2 D=3 D=4
One color forces the rest The following is forced. D=0 D=1 D=2 D=3 D=4
No edge between red or green vertices The following is forced. D=0 D=1 D=2 D=3 D=4
There is no simple way to find if a graph is 3- colorable: NPC D=0 D=1 D=2 D=3 D=4
2-colorable graphs are called Bipartite Two independent sets
The problem We are given a bipartite graph G(X,Y,E) with cost over the edges. |X|=|Y|. We want a minimum cost perfect matching 5 6 6 1 6 2 4 2 2 3
The problem We are given a bipartite graph G(X,Y,E) with cost over the edges. |X|=|Y|. We want a minimum cost perfect matching 1 2 2 2
A surprising solution using algebra only The LP is: Minimize e=(u,v) xec(e) Subject to: v|e=(u,v) E xe=1 xe 0
An optimal iterative rounding The LP is: Minimize e=(u,v) xec(e) xe is the fraction of e taken Subject to: v|e=(u,v) E xe=1 v has one neighbor Edges have non-negative values xe 0
A property of a BFS We shall show that every BFS has an entry that equals 1 or 0. Claim: If the claim holds, it implies that we can find a minimum cost matching using algebra only. Proof: As long as there is an edge e with xe=0, remove it from the graph and recompute the LP
We first show that this can be used to get an optimal solution It can t be that all edges have a value of 0. Eventually, there is an edge e with xe=1 Take e=(u,v) into our solution. Remove u,v, and their edges from the graph. Iterate with a new LP
We first show that this can be used to get an optimal solution Claim: The solution we get has a value that equals the value of the LP Proof: each iteration reduces the LP value by c(e) and adds c(e) cost to our solution. This means that our solution has a cost that equals the minimum LP value.
We first show that this can be used to get an optimal solution We know that optf opt and we just showed that optf=opt. This means that our solution is optimum. We now prove that every BFS has an entry 0 or 1.
The LP matrix: Vertices versus edges Consider the following graph AD AE BD BF CE CF 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 A B C D E F 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 C B A D E F
In A the rows are dependent Consider the following graph AD AE BD BF CE CF 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 A B C D E F 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 C B A D E F
This means that A cant contain all rows Consider the following graph AD AE BD BF CE CF 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 A B C D E F 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 C B A D E F
Because the rows of A,B,C have the same sum as the rows of D,E,F and is the all 1 Consider the following graph AD AE BD BF CE CF 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 A B C D E F 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 C B A D E F
It is true for any bipartite graph Consider the following graph AD AE BD BF CE CF 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 A B C D E F 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 C B A D E F
In the perfect matching problem let n be the number of vertices of every side Consider the following graph AD AE BD BF CE CF 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 A B C D E F 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 C B A D E F
The rank of this matrix is at most 2n-1 Consider the following graph AD AE BD BF CE CF 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 A B C D E F 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 C B A D E F
An optimal iterative rounding The LP is: Minimize e=(u,v) xec(e) Subject to: v|e=(u,v) E xe=1 xe 0
An optimal iterative rounding The LP is: Minimize e=(u,v) xec(e) xe is the fraction of e taken Subject to: v|e=(u,v) E xe=1 v has one neighbor Edges have non-negative values xe 0
Claim: every BFS has xe=0 or xe=1 for some e The LP is: Minimize e=(u,v) xec(e) xe is the fraction of e taken Subject to: v|e=(u,v) E xe=1 v has one neighbor Edges have non-negative values xe 0
Assume this is not the case The LP is: Minimize e=(u,v) xec(e) xe is the fraction of e taken Subject to: v|e=(u,v) E xe=1 v has one neighbor Edges have non-negative values xe 0
All tight constraints are v|e=(u,v) E xe=1 Note that there is a variable for every edge. Therefore in Ax=b the number of rows equals the number of edges (variables).
Assume for the sake of contradiction that this doesn t hold Claim: the number of edges in the graph is at least 2n Proof: Consider the set X (namely one of the two sides X and Y of the bipartite graph). Since all edges have fractional, values, every vertex is touched by at least two edges. At least two fractions are required to get a sum of 1.
