Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs

DOI10.1287/opre.2019.1956zbMath1445.90017arXiv1611.01210OpenAlexW3011858544MaRDI QIDQ5130515

Lee Breslau, Ilias Diakonikolas, Mohammad Taghii Hajiaghayi, Subhabrata Sen, Yu Gu, N. G. Duffield, David S. Johnson, Howard J. Karloff, Mauricio G. C. Resende

Publication date: 4 November 2020

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.01210

zbMATH Keywords

heuristicsfacility locationroutingnetwork tomographypath diversitynetwork measurementset cover by pairs

Mathematics Subject Classification ID

Integer programming (90C10) Communication networks in operations research (90B18) Discrete location and assignment (90B80)

Related Items

Set-weighted games and their application to the cover problem

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Algorithmic construction of sets for k -restrictions
• A threshold of ln n for approximating set cover
• Survivable IP network design with OSPF routing
• Genetic Algorithms and Random Keys for Sequencing and Optimization
• Disjoint-Path Facility Location: Theory and Practice
• Efficient probabilistically checkable proofs and applications to approximations
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• On the hardness of approximating spanners