Metraipolis › archive › dc_cdc1039fbc5a

Buy-at-Bulk Facility Location on Trees — arXiv:2608.26337

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.26337
License (as archived)
CC0-1.0
Archived
2026-10-17T19:18:20.531Z
SHA-256 of the archived text
da8984a6bef78ab15ac2c1544dd37085b0b82a69ae1c9487db0edaabda8905d7
Stable URL of this page
https://metraipolis.com/documento/dc_cdc1039fbc5a

How to cite

Buy-at-Bulk Facility Location on Trees — arXiv:2608.26337 — arXiv (en), https://arxiv.org/abs/2608.26337 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cdc1039fbc5a (Metraipolis archive dc_cdc1039fbc5a, sha256 da8984a6bef78ab15ac2c1544dd37085b0b82a69ae1c9487db0edaabda8905d7)
BibTeX
@misc{dccdc1039fbc5a,
  title = {Buy-at-Bulk Facility Location on Trees — arXiv:2608.26337},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.26337},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cdc1039fbc5a; sha256 da8984a6bef78ab15ac2c1544dd37085b0b82a69ae1c9487db0edaabda8905d7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.26337. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We consider the buy-at-bulk facility location problem (BBFL), a problem combining the classic facility location problem with buy-at-bulk network design, which finds motivation in telecommunication networks. In it, we are given a graph with edge lengths, opening costs and demands for each vertex, and a monotone and subadditive capacity-cost function, and our task is to open facilities on a subset of the vertices and route the demand from each vertex to these facilities. The cost of a solution (which we want to minimize) is given by the opening costs of the chosen facilities, plus the cost on each edge, which is given by its length times the cost of providing enough capacity for the demands through the edge, given by the capacity-cost function. A common variant of the problem, the $k$-cable facility location problem (kCFL), considers the case where capacity is provided by buying copies of given cable types, each with a certain capacity and cost. We study BBFL on tree instances and show, for the unit-demand and splittable variants, that the problem admits a PTAS (a $(1+\epsilon)$-approximation for any $\epsilon > 0$). We also consider kCFL in the new setting of cable-unsplittable demands, where the demand of a vertex cannot be split among multiple cables. We show that the problem is NP-hard to approximate to a factor better than $3/2$ on stars, and then provide an algorithm for tree instances that outputs a solution with optimal cost, but which exceeds the capacity on each cable by a factor of $1+\epsilon$. As a consequence, we show that the problem has a $2$-approximation algorithm on trees.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-28 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.26337 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T19:16:36.834Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).