30-10-2012, 05:10 PM
Efficient Algorithms for the Minimum Shortest Path Steiner Arborescence Problem with Applications to VLSI Physical Design
Efficient Algorithms.pdf (Size: 552.97 KB / Downloads: 57)
THE RSA/BNB/G ALGORITHM
Recently, Leung and Cong presented an exponential-time
branch-and-bound algorithm called RSA/BnB that solves the
MRSA problem optimally [22]. They observed that the RSA
heuristic is suboptimal precisely because Steiner mergers are
greedy and (sometimes) suboptimal. To obtain an optimal
solution, they suggested trying out both merging and skipping
at SMO’s. The algorithm, called RSA/BnB, essentially
enumerates the entire sequence of choices between merging
and skipping at each SMO, and [22] showed that this method
enumerates at least one optimal arborescence.
THE RSA/DP/G ALGORITHM
Leung and Cong [23] showed that each subproblem in the
recursive call to the RSA/BnB algorithm can be completely
characterized by a triple , which can be defined and
solved recursively. As a result, a hashing-based DP technique
can be applied to avoid computing any given subproblem more
than once. The algorithm, called RSA/DP, is significantly faster
than RSA/BnB and capable of solving 250-terminal MRSA
problems optimally in one hour. The reader may refer to [23]
for more details.
CONCLUSION
We have presented several efficient heuristics and exact
algorithms for the MSPSA problem, improving upon previous
work in both runtime and solution quality. We have also
presented detailed complexity analysis as well as extensive
experimental results that suggest that our algorithms are more
effective in practice than other arborescence algorithms. We
believe that applications to performance-driven global routing,
FPGA routing, and non-VLSI domains such as multicast
routing are all promising.