k-Anonymity　is　a　well-researched　privacy　principle　for　data　publishing.　It　requires　that　each　tuple　of　a　public　released　table　can　not　be　identified　with　a　probability　higher　than　1/k.　According　to　literatures,　one　way　to　achieve　k-anonymity　is　to　generalize　the　table　into　several　anonymization　groups.　All　tuples　within　a　group　is　indistinguishable.　However,　best　of　our　knowledge,　the　worst-case　upper　bound　on　size　of　anonymization　groups　resulting　from　existing　algorithms　is　not　good,　and　the　lowest　value　is　2k　-　1.　This　paper　propose　a　new　algorithm　for　k-anonymity　focusing　on　improving　the　solution　quality.　We　show　that　the　upper　bound　of　our　algorithm　is　lower　than　2k　-　1　in　non-trivial　cases,　and　when　n　＞　k2,　the　bound　becomes　k　+　1.　Experiments　on　real　world　dataset　demonstrate　our　conclusions.　©2010　IEEE.