The Demand-Matching Problem

References

• Bar-Noy A., Bar-Yehuda R., Freund A., Naor J., Schieber B. A unified approach to approximating resource allocation and scheduling. J. ACM (2001) 48(5):1069–1090Crossref, Google Scholar
• Berman P., Karpinski M. On some tighter inapproximability results. Proc. 26th Internat. Colloquium Automata, Languages Programming (1999) 200–209Crossref, Google Scholar
• Calinescu G., Chakrabarti A., Karloff H., Rabani Y. Improved approximation algorithms for resource allocation. Proc. 8th Conf. Integer Programming Combinat. Optim. (2002) 401–414Crossref, Google Scholar
• Chakrabarti A., Chekuri C., Gupta A., Kumar A. Approximation algorithms for the unsplittable flow problem. Proc. 5th Internat. Workshop Approximation Algorithms for Combinat. Optim. (2002) 51–66Crossref, Google Scholar
• Chekuri C. (2005) . Private communication, June 2005Google Scholar
• Chekuri C., Khanna S. A PTAS for the multiple knapsack problem. SIAM J. Comput. (2006) 35(3):713–728Crossref, Google Scholar
• Chekuri C., Mydlarz M., Shepherd F. B. Multicommodity demand flow on a tree. Proc. 30th Internat. Colloquium Automata, Languages Programming (2003) 410–425Crossref, Google Scholar
• Correa J., Goemans M. An approximate König’s theorem for edge coloring weighted bipartite graphs. Proc. 36th ACM Sympos. Theory of Comput. (2004) 398–406Crossref, Google Scholar
• Cosares S., Saniee I. An optimization problem related to balancing loads on SONET rings. Telecomm. Systems (1994) 3:165–181Crossref, Google Scholar
• Dinitz Y., Garg N., Goemans M. On the single-source unsplittable flow problem. Combinatorica (1999) 19:17–41Crossref, Google Scholar
• Du D. Z., Gao B., Hwang F. K., Kim J. H. On multirate rearrangeable Clos networks. SIAM J. Comput. (1998) 28:463–470Crossref, Google Scholar
• Edmonds J. Maximum matching and a polyhedron with 0, 1-vertices. J. Res. National Bureau Standards (B) (1965) 69:125–130Crossref, Google Scholar
• Farach M., Liberatore V. On local register allocation. Proc. 9th ACM-SIAM Sympos. Discrete Algorithms (1998) 564–573Google Scholar
• Garg N., Vazirani V., Yannakakis M. Primal-dual approximation algorithms for integral flow and multicut in trees with applications to matching and set cover. Algorithmica (1997) 18:3–20Crossref, Google Scholar
• Hoffman A., Kruskal J., Kuhn H., Tucker A. Integral boundary points of convex polyhedra. Linear Inequalities and Related Systems (1956) (Princeton University Press, Princeton, NJ) 223–246Google Scholar
• Ibarra O., Kim C. Fast approximation for the knapsack and sum of subset problems. J. ACM (1975) 22:463–468Crossref, Google Scholar
• Kleinberg J. Approximation algorithms for disjoint paths problems. (1996) . Ph.D. thesis, Department of EECS, MIT, Boston, MAGoogle Scholar
• Kleinberg J. Single-source unsplittable flow. Proc. 37th IEEE Sympos. Foundations Comput. Sci. (1996) 68–77Crossref, Google Scholar
• Kolliopoulos S. G., Stein C. Approximation algorithms for single-source unsplittable flow. SIAM J. Comput. (2002) 31:919–946Crossref, Google Scholar
• Kolliopoulos S. G., Stein C. Approximation disjoint-path problems using packing integer programs. Math. Programming Ser. A (2004) 99:63–87Crossref, Google Scholar
• Ngo H. Q., Vu V. H. On multirate rearrangeable Clos networks and a generalized edge coloring problem on bipartite graphs. SIAM J. Comput. (2003) 32(4):1040–1049Crossref, Google Scholar
• Papadimitriou C.Computational Complexity (1994) (Addison Wesley, Reading, MA) Google Scholar
• Shepherd F. B., Wilfong G. T. (2003) . Unpublished notes, JuneGoogle Scholar
• Shmoys D., Tardos É. An approximation algorithm for the generalized assignment problem. Math. Programming Ser. A (1993) 62:461–474Crossref, Google Scholar
• Skutella M. Approximating the single source unsplittable min-cost flow problem. Math. Programming Ser. B (2002) 91(3):493–514Crossref, Google Scholar
• Woeginger G. (2005) . Private communication. JanuaryGoogle Scholar