Tuesday, July 12, 2005

semidefinite programming for multi-dimensional scheduling

The mono-dimensional scheduling problem can be solved by a single linear programming problem. The multi-dimensional scheduling problem, however, requires multiple calls to the LP solver. The minimum number of LP calls is in the paper DRV-KMW. Can ZC be detected by using a SDP solver? Can MDS be done by a SDP solver? The latter is a harder problem as it also has to return the certificates (the rows of the schedule).

Fact: An edge can be on only path of the KMW-T. If it lies in a prime node, then there exists a ZC.

The scheduling matrix, can be constructed in other ways, like using KMW method (one LP call per edge) or KS method (n*logn LP calls).

To Do: Weak separation oracle from Lovasz's lecture notes (and also GLS:Grotschel-Lovasz-Schrijver book?). How to add quadratic constraints still preserving semidefiniteness.
SDP duality holds only under some regularity conditions. What are they?
To Do: SDP in mails
A Linear program is trivially a SDP. If a constraint of a LPP is of the form <= p, we can define a diagonal matrix A with A_i,i = a_i and we can also define a variable matrix X_i,i = x_i The resultant program is a SDP.
We could do a similar thing with the vectors q or X. What about the vector (1,-1) for the edges? The 2nd eigen values are non-+ve. which means that we cannot directly use that value. However, SDP only requires that the variable matrices are SD. not their coefficients.
Is this a SDP?
max sum_e z_e
z^2 <= 1
To do look up the different SDP formulations from Lovasz's notes.