Skip to main content
Log in

Coupled and k-sided placements: generalizing generalized assignment

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

In modern data centers and cloud computing systems, jobs often require resources distributed across nodes providing a wide variety of services. Motivated by this, we study the Coupled Placement problem, in which we place jobs into computation and storage nodes with capacity constraints, so as to optimize some costs or profits associated with the placement. The coupled placement problem is a natural generalization of the widely-studied generalized assignment problem, which concerns the placement of jobs into single nodes providing one kind of service. We also study a further generalization, the k-Sided Placement problem, in which we place jobs into k-tuples of nodes, each node in a tuple offering one of k services. For both the coupled and k-sided placement problems, we consider minimization and maximization versions. In the minimization versions (MinCPand Min \(k\)SP), the goal is to achieve minimum placement cost, while incurring a minimum blowup in the capacity of the individual nodes. Our first main result is an algorithm for Min \(k\)SP that achieves optimal cost while increasing capacities by at most a factor of \(k+1\), also yielding the first constant-factor approximation for MinCP. In the maximization versions (MaxCP and Max \(k\)SP), the goal is to maximize the total weight of the jobs that are placed under hard capacity constraints. Max \(k\)SP can be expressed as a k-column sparse integer program, and can be approximated to within a factor of O(k) factor using randomized rounding of a linear program relaxation. We consider alternative combinatorial algorithms that are much more efficient in practice. Our second main result is a local search based combinatorial algorithm that yields a 15-approximation and \(O(k^2)\)-approximation for MaxCP and Max \(k\)SP  respectively. Finally, we consider an online version of Max \(k\)SP and present algorithms that achieve logarithmic competitive ratio under certain necessary technical assumptions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Alvarez, G.A., Borowsky, E., Go, S., Romer, T.H., Becker-Szendy, R., Golding, R., Merchant, A., Spasojevic, M., Veitch, A., Wilkes, J.: Minerva: an automated resource provisioning tool for large-scale storage systems. Trans. Comput. Syst. 19, 483–518 (2001)

    Article  Google Scholar 

  2. Anderson, E., Hobbs, M., Keeton, K., Spence, S., Uysal, M., Veitch, A.: Hippodrome: running circles around storage administration. In: Proceedings of the Conference on File and Storage Technologies, pp. 175–188 (2002)

  3. Anderson, E., Kallahalla, M., Spence, S., Swaminathan, R., Wang, Q.: Quickly finding near-optimal storage designs. ACM Trans. Comput. Syst. 23, 337–374 (2005)

    Article  Google Scholar 

  4. Appleby, K., Fakhouri, S., Fong, L., Goldszmidt, G., Kalantar, M., Krishnakumar, S., Pazel, D.P., Pershing, J., Rochwerger, B.: Oceano-SLA based management of a computing utility. In: Proceedings of the International Symposium on Integrated Network Management, pp. 855–868 (2001)

  5. Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive on-line routing. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 32–40 (1993)

  6. Azar, Y., Epstein, A.: Convex programming for scheduling unrelated parallel machines. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing STOC’05, pp. 331–337 (2005)

  7. Bansal, N.: Personal communication (2014)

  8. Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: On \(k\)-column sparse packing programs. In: Proceedings of the Conference on Integer Programming and Combinatorial Optimization, pp. 369–382 (2010)

  9. Buchbinder, N., Naor, J.: Improved bounds for online routing and packing via a primal-dual approach. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21–24 October 2006, Berkeley, California, USA, Proceedings, pp. 293–304 (2006)

  10. Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comput. Sci. 3(2–3), 93–263 (2009)

    Article  MathSciNet  Google Scholar 

  11. Chase, J.S., Anderson, D.C., Thakar, P.N., Vahdat, A.M., Doyle, R.P.: Managing energy and server resources in hosting centers. In: Proceedings of the Symposium on Operating Systems Principles, pp. 103–116 (2001)

  12. Chekuri, C., Khanna, S.: A PTAS for the multiple knapsack problem. In: Proceedings of the Symposium on Discrete Algorithms, pp. 213–222 (2000)

  13. Cygan, M., Grandoni, F., Mastrolilli, M.: How to sell hyperedges: the hypermatching assignment problem. In: Symposium on Discrete Algorithms (SODA), pp. 342–351 (2013)

  14. Dowdy, L.W., Foster, D.V.: Comparative models of the file assignment problem. ACM Surv. 14, 287–313 (1982)

    Article  Google Scholar 

  15. Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum general assignment problems. In: Symposium on Discrete Algorithms (SODA), pp. 611–620 (2006)

  16. Harris, D., Srinivasan, A.: The Moser-Tardos framework with partial resampling, (2014, preprint). arXiv:1406.5943

  17. Harris, D.G., Srinivasan, A.: Constraint satisfaction, packet routing, and the Lovász Local Lemma. In: Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, 1–4 June 2013, pp. 685–694 (2013)

  18. Harris, D.G., Srinivasan, A.: The moser-tardos framework with partial resampling. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 469–478 (2013)

  19. Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20–39 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  20. Korupolu, M., Singh, A., Bamba, B.: Coupled placement in modern data centers. In: Proceedings of the International Parallel and Distributed Processing Symposium, pp. 1–12 (2009)

  21. Lau, L.C., Ravi, R., Singh, M.: Iterative Methods in Combinatorial Optimization. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (2011)

    Book  Google Scholar 

  22. Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(3), 259–271 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  23. Patterson, D.A.: Technical perspective: the data center is the computer. Commun. ACM 51, 105–105 (2008)

    Article  Google Scholar 

  24. Shmoys, D.B., Tardos, É.: An approximation algorithm for the generalized assignment problem. Math. Program. 62(3), 461–474 (1993)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

We would like to thank Aravind Srinivasan for helpful discussions, and for pointing us to the \({\varOmega }(k/\log k)\)-hardness result for k-set packing, in particular. We thank the anonymous referees for detailed insightful comments on earlier versions of the paper, and are especially grateful to a referee who generously offered a key insight leading to improved results for MinCP and Min \(k\)SP. We are thankful to Nikhil Bansal for pointing us to the recent results of Harris and Srinivasan on the Moser-Tardos framework for the Lovász Local Lemma, and their application to Min \(k\)SP. The third author was partly supported by awards NSF CNS-1217981 and CCF-1422715, and a Grant from ONR.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Rajmohan Rajaraman.

Additional information

A preliminary version of this paper appears in the Proceedings of the 17th Conference on Integer Programming and Combinatorial Optimization, 2014.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Korupolu, M., Meyerson, A., Rajaraman, R. et al. Coupled and k-sided placements: generalizing generalized assignment. Math. Program. 154, 493–514 (2015). https://doi.org/10.1007/s10107-015-0930-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-015-0930-1

Mathematics Subject Classification

Navigation