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

#### 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.
##### Scheda breve Scheda completa
2012
20th Annual European Symposium on Algorithms, ESA 2012
earnings; machine design; truthful mechanisms
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
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].
File allegati a questo prodotto
File
VE_2012_11573-559139.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Dimensione 204.33 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11573/559139`
• ND
• 5
• 5