betaFeedback

WorksComputer Science

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

Abstract

In nonuniform buy-at-bulk network design, we are given an undirected graph and hh 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⁡2h/(log⁡log⁡h)2)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⁡4h)O(\log^4 h) bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same O(log⁡2h/(log⁡log⁡h)2)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.

Paper details

vlnc:W_ua6sw4jh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…