http://nexus6.cs.ucla.edu/~cheese/survey.html. This is a paper by Alpert and Kahng entitled Recent Directions in Netlist Partitioning: A Survey. Students need not read (or download) sections 2.6, 3.5, 4.3, 4.4, 4.5, 5 and 6.Three questions: (pick one and answer it in a one-page essay that you will hand in to Prof. Itti the monday following the talk, at noon in class):
i. Explain the enhancements (changes) made by FM and Krishnamurthy to the KL algorithm, and the ramifications of these changes. ii. Describe a genetic algorithm approach to solve the problem of 2-way partitioning of graphs. In particular, suggest a crossover scheme and/or a measure of goodness. iii. Consider applying a SA approach to solve the 2-way partitioning problem on a circuit. Discuss the relationship between the cooling schedule, quality of the final result and run-time. How would you go about making trade-offs between these three quantities?
i. B. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Syst. Technical J., 49(2):291-307, 1970. ii. S. Kirkpatrick, C. Gelatt and M. Vecchi, Optimization by simulated annealing, Science, 220:671-680, 1983. iii. T. Bui and B. Moon, A fast and stable hybrid genetic algorithm for the ratio-cut partitioning problem on hypergraphs, Proc. Design Automation Conf., 664-669, 1994.