Primal-Dual-Based Algorithms for a Directed Network Design Problem

References

• Agrawal A., Klein P., Ravi R. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. (1995) 24:445–456Crossref, Google Scholar
• Edmonds J. Optimum branchings. J. Res. National Bureau Standards B (1967) 71:233–240Crossref, Google Scholar
• Frederickson G. N., Jaja J. Approximation algorithms for several graph augmentation problems. SIAM J. Comput. (1981) 10:270–283Crossref, Google Scholar
• Goemans M. X., Williamson D. P. A general approximation technique for constrained forest problem. SIAM J. Comput. (1995) 24:296–317Crossref, Google Scholar
• Goemans M. X., Goldberg A., Plotkin S., Shmoys D., Tardos E., Williamson D. P. Approximations algorithms for network design problems. Proc. 5th Annual Sympos. Discrete Algorithms (1994) (Association for Computing Machinery, New York) 223–232Google Scholar
• Held M., Karp R. The traveling-salesman problem and minimum spanning trees. Oper. Res. (1970) 18:1138–1162Link, Google Scholar
• Jain K. A factor 2 approximation algorithm for the generalized Steiner network problem. Proc. 39th Annual Sympos. Foundations Comput. Sci. (1998) Palo Alto, CA:448–457Crossref, Google Scholar
• Jain K., Vazirani V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Proc. 40th Annual Sympos. Foundations Comput. Sci. (1999) New York:2–13Google Scholar
• Melkonian V., Tardos É. Approximation algorithms for a directed network design problem. Proc. 7th Internat. Integer Programming Combin. Optim. Conf. (IPCO’99) (1999) Graz, Austria:345–360Crossref, Google Scholar
• Rajagopalan S., Vazirani V. On the bidirected cut relaxation for the metric Steiner tree problem. Proc. 10th Annual ACM-SIAM Sympos. Discrete Algorithms (1999) (Association for Computing Machinery, New York) 742–751Google Scholar
• Raz R., Safra S. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. Proc. 29th Annual ACM Sympos. Theory Comput. (1997) El Paso, Texas:475–484Crossref, Google Scholar
• Traveling salesman problem instances (2003) . TSPLIB libraryGoogle Scholar
• Williamson D. P., Goemans M. X., Mihail M., Vazirani V. A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica (1995) 15:435–454Crossref, Google Scholar
• Zhu A., Khuller S., Raghavachari B. A uniform framework for approximating weighted connectivity problems. Proc. 10th Annual Sympos. Discrete Algorithms (1999) (Association for Computing Machinery, New York) 937–938Google Scholar