Metraipolis › archive › dc_a7d8ffb7f233

Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap — arXiv:2611.06894

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.06894
License (as archived)
CC0-1.0
Archived
2026-11-05T18:31:44.442Z
SHA-256 of the archived text
c8cd4289bca8057da24ecb7c7b158be93fadd2cae0fcc20b8d362625ef2f506c
Stable URL of this page
https://metraipolis.com/documento/dc_a7d8ffb7f233

How to cite

Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap — arXiv:2611.06894 — arXiv (en), https://arxiv.org/abs/2611.06894 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a7d8ffb7f233 (Metraipolis archive dc_a7d8ffb7f233, sha256 c8cd4289bca8057da24ecb7c7b158be93fadd2cae0fcc20b8d362625ef2f506c)
BibTeX
@misc{dca7d8ffb7f233,
  title = {Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap — arXiv:2611.06894},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06894},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a7d8ffb7f233; sha256 c8cd4289bca8057da24ecb7c7b158be93fadd2cae0fcc20b8d362625ef2f506c},
  year = {2026}
}

Archived text

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

In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network resource has two independent parameters: a fixed buying price paid once if the resource is used, and a per-unit rental cost (or physical length) paid proportionally to the traffic it carries. Unlike the uniform-cost or single-sink variants, the general multicommodity problem allows unrelated buying and rental metrics across arbitrary source--sink pairs, arbitrary demands, and both edge and node resources. We give a deterministic polynomial-time $O(\log^2 h / (\log\log h)^2)$-approximation algorithm for undirected nonuniform buy-at-bulk network design. The guarantee holds for edge costs, node costs, and their combination, and applies to arbitrary positive rational demands with no dependence on the number of vertices or the numerical demand ratio. This improves upon the $O(\log^4 h)$ bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same $O(\log^2 h / (\log\log h)^2)$ upper bound on the integrality gap of the natural affine multicommodity flow LP, bounding integral buying and rental costs separately against their fractional counterparts and preserving zero rental budgets exactly.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.06894 — 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-11-05T18:21:04.032Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).