Improved algorithms cut costs for complex network design problems
Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap
Data Structures and Algorithms
Summary
The paper studies a problem where a network must handle multiple pairs of locations needing connections with varying amounts of traffic, while balancing the cost to buy network resources and the cost to use them. The authors improve how closely a computer algorithm can approximate the cheapest way to build and use the network when costs vary widely between connections. They also show their method closely matches how well a mathematical relaxation can estimate the true optimum. This means network planners can better understand the trade-offs and plan more cost-effective communication or transportation networks.
What this means in practice
- •For network infrastructure planners: Design cost-efficient communication or transportation networks facing varied and complex usage demands with better cost guarantees.
- •For telecommunications engineers: Optimize multiservice network resource allocation by incorporating both fixed infrastructure costs and usage-based costs in heterogeneous network settings.
Authors
Iman Gholami, MohammadTaghi Hajiaghayi
Abstract
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.