Unitary graph scheduling problem

Approaches:

All pair shortest paths
max-flow?
--

LP formulations of the computability/scheduling problem

Motivation: Given that we have a matrix of size (n+d)*m which contains the components {0,+1,-1}. There are many ways in which we can formulate a linear program with this matrix somehow acting as constraints. Let us observe the different ways we can do so, for a close enough look at the linear programs may yield insights into the unitary graph scheduling problem.

Standard/state-of-the-art way (as in Darte-Vivien): Associate the variables of the LP problem to the columns of the matrix. We have m variables in the LP program. This can be thought of as (i) associating variables to edges of the hypergraph and also, (ii) associating variables to the edge-vertices of the bipartite graph. If a hyperedge has a zero component, we throw it away before sending it to next level.

Dual problem with n variables: What if we associate weights with vertices of the RDG? then we somehow can obtain the depth that node is disassociated with the rest of the graph. This is the matrix that Darte-Vivien use for scheduling at every level.

Dual problem with (n+d) variables: This has not been previously expored. We associate a variable to each of the (n+d) "vertices" of the bipartite graph.

many constraints:What if we associate weights with edges of the bipartite graph? There will be (n+d)*m elements we have to find.

Using the decomposition tree: Assume that the decomposition tree is given to us. How do you find the schedule component for each of the variables at that depth?

--
Bipartite matching Tarjan's algorithm and Hopcroft-Karp's matching algorithm, and Vazirani's algorithm. What is the connection between Bipartite matching and SURE scheduling?

Hall's theorem and its variants from Khuller's notes. Hypergraph basics from Berge's book.

--
What does a zero weight cycle in th RDG meain the hypergraph. What does it mean in the bipartite graph?

How does the EDG of the hypergraph look like?

How does the EDG of the hypergraph look like? What are the vertices, what are the edges?

A zero weight cycle in the EDG corresponds to the computability problem of the usual SURE. When does a "node" in the hypergraph-EDG have to wait for infinite time before its computation starts?

(taking a cue from KMW in their statement/proof of colrollary1) What if we think the n vertices also as the dimensions? so the computability problem is a URE in n+d dimensions. How do you label the 'n' to be similar to the 't'? You may want to use this in proving some properties of the URE. The example are lower/upper bound for the schedule. lower/upper bound for the memory allocation.

When does the hyper-EDG have a node which has an infinite length path ending in it?

If loops in the EDG are hindering you, forget them for a moment.

It is clear that the usual EDG has the linearity implicitly embedded in the structure of the polyhedron. We are somehow destroying it by using the hypergraph representation.

Possible correspondence: All this is ok. but, given a hyper-RDG, How do you reconstruct the EDG? vertices of the hyper-RDG: For each of the vertices of the hyper-RDG, we have a corresponding vertex at every point in F_n. Edges of the hyper-RDGIn the hRDG, if vertices v1 and v2 participate in an edge h_e -- which will actually be used a function, returning a set of vertices of the hypergraph, the V (meaning v_h and v_t), exactly 2 and the W set, represented by w_i --, then there is a edge between vertices (v_h,z) and (v_t,z-z') with z' being a d dimensional vector and z'_i = 1 if d_i belongs to the set W and z'_i = 0, if d_i does not belong to W.

What does incomputability mean in the hRDG? A vertex v_i of the hRDG is computable if there exists a path of infinite length ending in it.
--

How hard is the Software-pipelining problem (If it is NPO, what is the best approximation algorithm possible)?

How hard is the SURE scheduling problem? Can we do faster for a special case?

How hard is the SARE scheduling problem?
--
Is it possible to obtain a Theta((n+d)*m) multi-dimensional scheduling algorithm (or even faster)?
--
The algorithm for maximum matching also -- like max flow problem -- seems to use the idea of augmenting pathsRead this link
--
Ideas for Polynomial schedules (possibly better than linear schedules and are a kind of free schedules)
If we divide the vertices of the hypergraph into actual-vertices and dependence-vertices, it is clear that, if a AV does not have an path of length 1 from one DV, then that AV can be computed independent of that dependence component. OTOH, if a AV does not have a path of length 1 to one DV, then the AV can be computed....

Also, if an AV is is not connected to a DV, then that component of AV can be computed independent of that DV. If so, that vertex has a schedule that is a polynomial of better degree that rest of the vertices. If no vertices exist which satisfy these conditions, then the best polynomial schedule has degree of d.