Title :
A Randomized Greedy Algorithm for the Pattern Fill Problem for DFM Applications
Author :
Mukherjee, Maharaj ; Chakraborty, Kanad
Author_Institution :
IBM Res., Hopewell Junction
Abstract :
This work deals with the dummy fill and negative fill insertion problem with constraints on the minimum and maximum pattern density within a moving rectangular window. It is shown that the general class of such problems is at least NP-hard. A greedy randomized algorithm for this problem is proposed, and its proof of convergence and some experimental results are presented. More detailed account of our implementation and results are available in [7].
Keywords :
design for manufacture; greedy algorithms; design for manufacture; dummy fill insertion; greedy algorithm; negative fill insertion; Algorithm design and analysis; Containers; Convergence; Design for manufacture; Greedy algorithms; Manufacturing; Planarization; Resists; Shape; USA Councils;
Conference_Titel :
Quality Electronic Design, 2008. ISQED 2008. 9th International Symposium on
Conference_Location :
San Jose, CA
Print_ISBN :
978-0-7695-3117-5
DOI :
10.1109/ISQED.2008.4479753
