k-Anonymity　is　a　famous　and　widely　used　privacy　principle　for　protecting　private　information.　It　requires　that　each　tuple　of　a　public　released　data　table　must　be　indistinguishable　from　at　least　other　k　-　1　tuples.　Given　a　table,　finding　an　optimal　k-anonymous　version　is　NP-hard　in　most　previous　recoding　＇model＇.　Thus,　designing　an　efficient　algorithm　to　find　high-quality　kanonymous　version　is　still　challenge,　though　k-anonymity　is　well-researched.　In　recent　years,　hierarchical　partition　is　proposed　and　widely　accepted.　Viewing　the　given　table　as　a　multidimensional　space,　each　hierarchical　partition　of　the　space　is　a　multidimensional　recoding　under　some　special　constraints.　Previous　works　need　huge　computation　to　find　optimal　hierarchical　partition,　and　efficient　algorithms　just　find　a　reasonable　hierarchical　partition.　In　this　paper,　we　show　that　optimal　hierarchical　partition　for　k-anonymity　can　be　obtained　within　polynomial　time　when　a　fixed　quasi-identifier　is　given.　We　then　design　a　bottom-up　algorithm　using　dynamic　approach.　Through　theoretical　analysis　and　experiments,　we　show　that　our　algorithm　finds　better　results　than　related　works,　and　our　algorithm　runs　significantly　fast　comparing　with　other　optimal　algorithms　for　hierarchical　partition.　©2010　IEEE.