I detta papper ger vi förbättrad approximation algoritmer för MinMax Tree Cover och Bounded Tree Cover problem. Med tanke på en graf G = (V, E) med vikter w : I Min-Max k-tree Cover problem vi ges graf G och ett positivt heltal k och målet är att hitta en trädtäcke med k träd, så att vikten av det största trädet i omslaget minimeras. Vi presenterar en 3- approximation algoritm för detta förbättra de två olika approximation algoritmer som presenteras i Lett. 38:169-173, 2010).......................................................................................... I Bounded Tree Cover problem får vi graf G och en bunden λ och målet är att hitta en trädtäcke med minsta antal träd så att varje träd har vikt som mest λ. Vi presenterar en 2,5- approximation algoritm för detta, förbättra 3- approximation bundna i Arkin et al. (J. Algoritmer 59:1-18, 2006).
För min-max trädtäcke med k träd, Khani och Salavatipour REF förbättrade senare approximationsgarantin till en faktor av tre.
Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}