Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
<|reference_start|>Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing: We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results.   We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [CHKS09,KN11]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [CHKS09]. The rounding is based on recent results in hop-constrained oblivious routing [GHZ21], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to hop constrained network design for which we obtain LP-based bicriteria approximation algorithms.   We also consider a fault-tolerant version of hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [GL17,GML18,AJL20] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail.<|reference_end|>
@article{chekuri2024approximation,
    title={Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network
  Design via Hop Constrained Oblivious Routing},
    author={Chandra Chekuri, Rhea Jain},
    journal={arXiv preprint arXiv:2404.16725},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.16725},
    primaryClass={cs.DS}
}