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

References

• Aho AV, Hopcroft JE, Ullman JD (1974) The Design and Analysis of Computer Algorithms (Addison-Wesley Publishing Company, Reading, MA).Google Scholar
• Alon N, Moshkovitz D, Safra S (2006) Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms 2(2):153–177.Crossref, Google Scholar
• Bean J (1994) Genetics and random keys for sequencing and optimization. ORSA J. Comput. 6(2):154–160.Link, Google Scholar
• Bellare M, Goldwasser S, Lund C, Russell A (1993) Efficient probabilistic checkable proofs and applications to approximation. Kosaraju R, Johnson DS, Aggarwal A, eds. Proc. 25th Annual ACM Sympos. Theory Comput. (Assocation for Computing Machinery, New York), 294–304.Google Scholar
• Breslau L, Chase C, Duffield N, Fenner B, Mao Y, Sen S (2006) VMScope—A virtual multicast VPN performance monitor. ACM SIGCOMM Workshop Internet Network Management (INM) (Assocation for Computing Machinery, New York), 59–64.Google Scholar
• Breslau L, Diakonikolas I, Duffield N, Gu Y, Hajiaghayi M, Johnson DS, Karloff H, Resende MGC, Sen S (2011) Disjoint-path facility location: Theory and practice. Müller-Hannemann M, Werneck R, eds. Proc. 11th Annual Workshop Algorithm Engrg. Experimentation (ALENEX), 60–74.Google Scholar
• Burch H, Chase C (2005) Monitoring link delays with one measurement host. Performance Evaluation Rev. 33(3):10–17.Crossref, Google Scholar
• Buriol LS, Resende MGC, Thorup M (2007) Survivable IP network design with OSPF routing. Networks 49(1):51–64.Crossref, Google Scholar
• Calvert K, Doar M, Zegura E (1997) Modeling internet topology. IEEE Comm. Magazine 35(6):160–163.Crossref, Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Google Scholar
• Fortz B, Thorup M (2000) Internet traffic engineering by optimizing OSPF weights. Proc. INFOCOM: 19th Annual Joint Conf. IEEE Comput. Comm. Soc. (Institute of Electrical and Electronics Engineers, New York), 519–528.Google Scholar
• Gonçalves JF, Resende MGC (2011) Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17(5):487–525.Crossref, Google Scholar
• Gu Y, Breslau L, Duffield N, Sen S (2008) GRE encapsulated multicast probing: A scalable technique for measuring one-way loss. IEEE Infocom 2008: 27th Conf. Comput. Comm. (Institute of Electrical and Electronics Engineers Communications Society, New York), 1651–1659.Google Scholar
• Hassin R, Segev D (2005) The set cover with pairs problem. Ramanujam R, ed. FSTTCS 2005: Proc. 25th Internat. Conf. Foundations Software Tech. Theoretical Comput. Sci., Lecture Notes in Computer Science, vol. 3821, (Springer-Verlag, Berlin), 164–176.Google Scholar
• Johnson DS (1974) Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9(3):256–278.Crossref, Google Scholar
• Kortsarz G (2001) On the hardness of approximating spanners. Algorithmica 30(3):432–450.Crossref, Google Scholar
• Lovász L (1975) On the ratio of optimal integral and fractional covers. Discrete Math. 13(4):383–390.Crossref, Google Scholar
• Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. Leighton FT, Shor P, eds. Proc. 29th Annual ACM Sympos. Theory Comput. (Association of Computing Machinery, New York), 475–484.Google Scholar