I have a graph optimization problem which is hard to describe in the title.

There is a component based system which consists of components and data transmissions between components(components and data transmissions will be represented by BC for short). The system has only one entry and one exit which means the system will always execute from the start component to the end component. Suppose the system only has sequence and concurrence structures. In sequence structure, the components execute one by one. In concurrence structure, components in different branches execute at the same time.

Each component and data transmission has a response time $a_i$. Now I have $k$ resources. Each resource can only be allocated to one BC. If a BC has a resource, its response time will drop from $a_i$ to $b_i$. I can calculate the response time of the system because response time in sequence structure can be added up and it will be the max in concurrence structures. So I can get the system response time if I know all the BC's response time.

Now I need to know what is the best resource allocation strategy to make the system response time minimum?

The system can be represented as a graph $S$ which has $n$ nodes and edges(BC for short). The nodes represent components and the edges represent data transmissions. The graph has only one entry and one exit and all the edges are in one direction. $S=\{BC_1,BC_2,\ldots, BC_n\}$. $BC_i$ has two values $a_i, b_i$. $a_i$ means the normal response time. $b_i$ means the response time when allocated a resource.

I have a function to calculate the response time of any graph $G$ which time complexity is $O(n)$ (n is the number of edges and nodes it contains). A naive method is choose the best from $\binom nk$ different allocations. So the time complexity is $O(n \cdot \binom nk)$.

Now I think I can use dynamic programming to solve this problem. My idea is to treat a complex structure as a node then some intermediate results can be cached. I have some images to describe my idea. For example, the graph $S$ can be represented as $N_1,E_A,N_A,E_B,N_3$. The best allocation must come from the 11 different allocations. I can cache the result of allocating $0,1,2$ resource to $N_A$ to avoid repetitive computation. If not, $F(N_A, 0)$ will be calculated 6 times by simply enumerating.

I think my solution's time complexity is better than $n \cdot \binom nk$. However I don't know how to prove it. Intuitively I think my solution is solvable in polynomial time.

Treat the concurrence structure as a node which can hold 6 resources. Treat the up branch and down branch as a node which can hold 3 resources respectively

  • $\begingroup$ What are sequence and concurrence structures? If they are what I think they are, then your graph is a series parallel graph. Such graphs have treewidth $2$, and it might very well be that your algorithm is a special case of dynamic programming on tree decompositions. You should provide a bit more detail in your question, as it isn't clear how the value of an assignment is computed, and I don't understand your proposed algorithm either. $\endgroup$ – Tom van der Zanden May 9 '15 at 19:09
  • $\begingroup$ hi, i have added more details. Would you give more suggestions? $\endgroup$ – Dong May 10 '15 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.