Reproduce “Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Iman Gholami, MohammadTaghi Hajiaghayi
The authors give a deterministic polynomial-time approximation for undirected nonuniform buy-at-bulk routing with arbitrary rational demands. The algorithm processes requests across cost scales, reusing bought connections or buying paths, and rounds the natural affine multicommodity-flow LP with separate buying and rental bounds. For h≥3, its factor is O(log² h/(log log h)²), improving the prior O(log⁴ h) guarantee, independent of graph size and demand ratio.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.