Tight Approximation Algorithms for Maximum Separable Assignment Problems

References

• Ageev A. A., Sviridenko M. I. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Combin. Optim. (2004) 8:307–328Crossref, Google Scholar
• Andelman N., Mansour Y. Auctions with budget constraints. Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT) (2004) (Springer, Berlin) 26–38Google Scholar
• Baev I. D., Rajaraman R. Approximation algorithms for data placement in arbitrary networks. Proc. 12th ACM-SIAM Sympos. Discrete Algorithms (SODA) (2001) (Society for Industrial and Applied Mathematics, Philadelphia) 661–670Google Scholar
• Baev I. D., Rajaraman R., Swamy C. Approximation algorithms for data placement problems. SIAM J. Comput. (2008) 38(4):1411–1429Crossref, Google Scholar
• Beniaminy I., Nutov Z., Yuster R. A (1-1/e)-approximation algorithm for the maximum generalized assignment problem with fixed profits. Oper. Res. Lett. (2006) 34:283–288Crossref, Google Scholar
• Calinescu G., Chekuri C., Pal M., Vondrak J. Maximizing a submodular set function subject to a matroid constraint. SIAM J. Comput. (2010) . ForthcomingGoogle Scholar
• Carr B., Vempala S. Randomized meta-rounding. Random Structure and Algorithms (2002) 20(3):343–352Crossref, Google Scholar
• Chakrabarty D., Goel G. On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and gap. Proc. 49th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (2008) (IEEE Computer Society, Los Alamitos, CA) 687–696Google Scholar
• Chekuri C. (2005) . Personal communicationGoogle Scholar
• Chekuri C., Khanna S. A PTAS for the multiple knapsack problem. Proc. 11th ACM-SIAM Sympos. Discrete Algorithms (SODA) (2000) 213–222Google Scholar
• Feige U. A threshold of ln n for approximating set cover. J. ACM (1998) 45(4):634–652Crossref, Google Scholar
• Feige U., Halldorsson M. M., Kortsarz G., Srinivasan A. Approximating the domatic number. SIAM J. Comput.32(1):172–195Google Scholar
• Feige U., Kortsarz G. (2005) . Personal communicationGoogle Scholar
• Feige U., Vondrak J. Approximation algorithms for allocation problems: Improving the factor of 1-1/e. Proc. 47th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (2006) (IEEE Computer Society, Los Alamitos, CA) Google Scholar
• Fisher M. L., Nemhauser G. L., Wolsey L. A. An analysis of the approximations for maximizing submodular set functions II. Math. Programming Stud. (1978) 8:73–87Crossref, Google Scholar
• Fleischer L., Goemans M., Mirrokni V. S., Sviridenko M. Tight approximation algorithms for maximum general assignment problems. Proc. 16th Annual ACM/SIAM Sympos. Discrete Algorithms (SODA)(Society for Industrial and Applied Mathematics, Philadelphia) 611–620Google Scholar
• Garg N., Könemann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. Proc. 39th Annual IEEE Sympos. Foundations Comput. Sci. (1998) (IEEE Computer Society, Los Alamitos, CA) 300–309Google Scholar
• Garg R., Kumar V., Pandit V. Approximation algorithms for budget-constrained auctions. Proc. 4th Internat. Workshop on Approximation Algorithms for Combin. Optim. Problems (APPROX) (2001) (Society for Industrial and Applied Mathematics, Philadelphia) Google Scholar
• Goemans M. X., Williamson D. P. New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math.7:656–666Google Scholar
• Gomes C., Regis R., Shmoys D. An improved approximation algorithm for the partial Latin square extension problem. Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA) (2003) (Society for Industrial and Applied Mathematics, Philadelphia) Google Scholar
• Jain K., Mahdian M., Salavatipour M. Packing steiner trees. Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA) (2003) (Society for Industrial and Applied Mathematics, Philadelphia) 266–274Google Scholar
• Jansen K., Zhang G. On rectangle packing: Maximizing benefits. Proc. 15th ACM-SIAM Symp. Discrete Algorithms (SODA) (2004) (Society for Industrial and Applied Mathematics, Philadelphia) 204–213Google Scholar
• Mirrokni V. S.Approximation Algorithms for Distributed and Selfish Agents (2005) (Massachusetts Institute of Technology, Cambridge, MA) Google Scholar
• Petrank E. The hardness of approximation: Gap location. Comput. Complexity (1994) 133–137Crossref, Google Scholar
• Plotkin S. A., Shmoys D., Tardos É. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. (1995) 20:257–301Link, Google Scholar
• Shachnai H., Tamir T. Approximation schemes for generalized 2-dimensional vector packing with application to data placement. Proc. 6th Internat. Workshop on Approximation Algorithms for Combinat. Optim. Problems (APPROX) (2003) (Springer, Berlin) 167–177Google Scholar
• Shmoys D., Tardos E. An approximation algorithm for the generalized assignment problem. Math. Programming (1993) 62(3):461–474Crossref, Google Scholar
• Sviridenko M. A note on maximizing a submodular set function subject to knapsack constraint. Oper. Res. Lett. (2004) 32:41–43Crossref, Google Scholar
• Vondrák J. Optimal approximation for the submodular welfare problem in the value oracle model. Proc. 4th Annual ACM Sympos. Theory Comput. (STOC) (2008) (ACM, New York) 67–74Google Scholar
• Young N. Randomized rounding without solving the linear program. Proc. 7th ACM-SIAM Sympos. Discrete Algorithms (SODA) (1996) (Society for Industrial and Applied Mathematics, Philadelphia) 170–178Google Scholar
• Young N. Sequential and parallel algorithms for mixed packing and covering. Proc. 42nd Annual IEEE Sympos. Foundations Comput. Sci. (2001) (IEEE Computer Society, Los Alamitos, CA) 538–546Crossref, Google Scholar