Monday, July 18, 2005

semidefinite programming and MDS approaches

There are many ways in which we can approach to formulate the ZC-D or MDS using SDP. Here are the approaches for ZCD.
Method1: Begin with an approach similar to the LP formulation. define a diagonal matrix X such that diag(X) = x, where x is the x of CM-Z (or q of DV-KMW) To recap, x in CM-Z determined the number of times an edge is taken in a ZC. Also define (n+d) diagonal matrices A_k such that diag(A_k) = Kth_row(A), where A is the same as A of CM-Z (or B of DV-KMW). Just to recap, A in CM-Z had as the first n rows, the incidence matrix of the graph and has as the next n rows, the d-dimensional weight vectors associated with the edges.
The resultant "SDP" is the following:
min X
A_k @ X = 0
forall k = 1...d
where A_k and X are all diagonal matrices.
//A and X belong to M_(m)
min X
s.t A_k @ X >>= 0
forall k = 1...d
where A_k is the adjacency matrix of the kth component of the dependence components.
This method raises many questions:
A_k is not a symmetric matrix. Can we make it a symmetric matrix, using a discrete Lyapunov kind of equality?
What does that mean for the matrix X??

To Do:Look up the spectral graph theory book to find how weights on the edges are represented.
What is the meaning of the eigen values of a weighed directed graph? How do you interpret it with respect to any of the known graph algorithms?