Metal　fill　insertion　has　become　an　essential　step　in　reducing　dielectric　thickness　variation　and　improving　pattern　uniformity,　which　is　important　in　mitigating　process　variations,　thereby　achieving　better　manufacturing　yield.　However,　metal　fills　could　induce　coupling　capacitance,　which　is　not　often　considered　in　existing　works　that　typically　focus　more　on　pattern　density　uniformity,　incurring　significant　problems　in　timing　closure.　However,　it　is　a　great　challenge　to　consider　three　types　of　capacitances　(i.e.,　area,　fringe,　and　lateral　capacitances)　with　design　rules　and　density　constraints　at　the　fill　insertion　stage　simultaneously.　This　article　presents　an　efficient　timing-aware　fill　insertion　algorithm　for　minimizing　the　total　capacitance　and　fill　amount,　considering　the　density　constraints.　First,　we　present　an　initial　metal　fill　insertion　and　design-rule-aware　legalization　to　obtain　an　initial　fill　insertion　solution　quickly.　Second,　from　critical　conductors　to　powers/grounds　in　a　circuit,　we　divide　conductors　into　different　equivalent　paths　and　then　construct　a　capacitance　graph　to　reduce　the　capacitance　of　each　equivalent　path　globally.　Third,　we　propose　a　density-aware　coupling　capacitance　optimization　method　and　a　fast　Monte　Carlo-based　fill　selection　to　further　reduce　the　coupling　capacitance　between　any　pair　of　conductors.　Finally,　we　present　a　density-aware　fill　deletion　method　to　reduce　the　fill　amount.　We　evaluate　the　performance　of　our　algorithm　on　the　benchmarks　of　the　2018　CAD　Contest　at　ICCAD　and　its　official　contest　evaluator.　Compared　with　the　first-place　team　of　the　contest　and　the　state-of-the-artwork,　experimental　results　show　that　our　algorithm　achieves　the　lowest　total　capacitance　and　the　least　fill　amount　in　a　comparable　runtime.　©　1982-2012　IEEE.