In this paper we focus on problems characterized by an input n-node tree and a collection of subpaths. Motivated by the fact that some of these problems admit a very good approximation (or even a poly-time exact algorithm) when the input tree is a path, we develop a decomposition theorem of trees into paths. Our decomposition allows us to partition the input problem into a collection of O(loglogn) subproblems, where in each subproblem either the input tree is a path or there exists a hitting set F of edges such that each path has a non-empty, small intersection with F. When both kinds of subproblems admit constant approximations, our method implies an O(loglogn) approximation for the original problem. We illustrate the above technique by considering two natural problems of the mentioned kind, namely Uniform Tree Tollbooth and Unique Tree Coverage. In Uniform Tree Tollbooth each subpath has a budget, where budgets are within a constant factor from each other, and we have to choose non-negative edge prices so that we maximize the total price of subpaths whose budget is not exceeded. In Unique Tree Coverage each subpath has a weight, and the goal is to select a subset X of edges so that we maximize the total weight of subpaths containing exactly one edge of X. We obtain O(loglogn) approximation algorithms for both problems. The previous best approximations are O(logn/loglogn) by Gamzu and Segev [ICALP'10] and O(logn) by Demaine et al. [SICOMP'08] for the first and second problem, respectively, however both previous results were obtained for much more general problems with arbitrary budgets (weights). © 2012 Springer-Verlag.
A path-decomposition theorem with applications to pricing and covering on trees / Cygan, Marek; Fabrizio, Grandoni; Leonardi, Stefano; Marcin, Pilipczuk; Piotr, Sankowski. - 7501 LNCS:(2012), pp. 349-360. (Intervento presentato al convegno 20th Annual European Symposium on Algorithms, ESA 2012 tenutosi a Ljubljana; Slovenia) [10.1007/978-3-642-33090-2_31].
A path-decomposition theorem with applications to pricing and covering on trees
LEONARDI, Stefano;
2012
Abstract
In this paper we focus on problems characterized by an input n-node tree and a collection of subpaths. Motivated by the fact that some of these problems admit a very good approximation (or even a poly-time exact algorithm) when the input tree is a path, we develop a decomposition theorem of trees into paths. Our decomposition allows us to partition the input problem into a collection of O(loglogn) subproblems, where in each subproblem either the input tree is a path or there exists a hitting set F of edges such that each path has a non-empty, small intersection with F. When both kinds of subproblems admit constant approximations, our method implies an O(loglogn) approximation for the original problem. We illustrate the above technique by considering two natural problems of the mentioned kind, namely Uniform Tree Tollbooth and Unique Tree Coverage. In Uniform Tree Tollbooth each subpath has a budget, where budgets are within a constant factor from each other, and we have to choose non-negative edge prices so that we maximize the total price of subpaths whose budget is not exceeded. In Unique Tree Coverage each subpath has a weight, and the goal is to select a subset X of edges so that we maximize the total weight of subpaths containing exactly one edge of X. We obtain O(loglogn) approximation algorithms for both problems. The previous best approximations are O(logn/loglogn) by Gamzu and Segev [ICALP'10] and O(logn) by Demaine et al. [SICOMP'08] for the first and second problem, respectively, however both previous results were obtained for much more general problems with arbitrary budgets (weights). © 2012 Springer-Verlag.File | Dimensione | Formato | |
---|---|---|---|
VE_2012_11573-559139.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
204.33 kB
Formato
Adobe PDF
|
204.33 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.