Sequential Testing with Subadditive Costs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912210477907968 |
|---|---|
| author | Harris, Blake Nagarajan, Viswanath Tan, Rayen |
| author_facet | Harris, Blake Nagarajan, Viswanath Tan, Rayen |
| contents | In the classic sequential testing problem, we are given a system with several components each of which fails with some independent probability. The goal is to identify whether or not some component has failed. When the test costs are additive, it is well known that a greedy algorithm finds an optimal solution. We consider a much more general setting with subadditive cost functions and provide a $(4ρ+γ)$-approximation algorithm, assuming a $γ$-approximate value oracle (that computes the cost of any subset) and a $ρ$-approximate ratio oracle (that finds a subset with minimum ratio of cost to failure probability). While the natural greedy algorithm has a poor approximation ratio in the subadditive case, we show that a suitable truncation achieves the above guarantee. Our analysis is based on a connection to the minimum sum set cover problem. As applications, we obtain the first approximation algorithms for sequential testing under various cost-structures: $(5+ε)$-approximation for tree-based costs, $9.5$-approximation for routing costs and $(4+\ln n)$ for machine activation costs. We also show that sequential testing under submodular costs does not admit any poly-logarithmic approximation (assuming the exponential time hypothesis). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_18010 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sequential Testing with Subadditive Costs Harris, Blake Nagarajan, Viswanath Tan, Rayen Data Structures and Algorithms In the classic sequential testing problem, we are given a system with several components each of which fails with some independent probability. The goal is to identify whether or not some component has failed. When the test costs are additive, it is well known that a greedy algorithm finds an optimal solution. We consider a much more general setting with subadditive cost functions and provide a $(4ρ+γ)$-approximation algorithm, assuming a $γ$-approximate value oracle (that computes the cost of any subset) and a $ρ$-approximate ratio oracle (that finds a subset with minimum ratio of cost to failure probability). While the natural greedy algorithm has a poor approximation ratio in the subadditive case, we show that a suitable truncation achieves the above guarantee. Our analysis is based on a connection to the minimum sum set cover problem. As applications, we obtain the first approximation algorithms for sequential testing under various cost-structures: $(5+ε)$-approximation for tree-based costs, $9.5$-approximation for routing costs and $(4+\ln n)$ for machine activation costs. We also show that sequential testing under submodular costs does not admit any poly-logarithmic approximation (assuming the exponential time hypothesis). |
| title | Sequential Testing with Subadditive Costs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.18010 |