Document Open Access Logo

Generalized Assignment via Submodular Optimization with Reserved Capacity

Authors Ariel Kulik, Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.69.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Ariel Kulik
  • Computer Science Department, Technion, Haifa, Israel
Kanthi Sarpatwar
  • IBM Research, Yorktown Heights, NY, USA
Baruch Schieber
  • Department of Computer Science, New Jersey Institute of Technology, Newark, NJ, USA
Hadas Shachnai
  • Computer Science Department, Technion, Haifa, Israel

Acknowledgements

H. Shachnai’s work was conducted during a visit to DIMACS partially supported by the National Science Foundation under grant number CCF-1445755.

Cite As Get BibTex

Ariel Kulik, Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. Generalized Assignment via Submodular Optimization with Reserved Capacity. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 69:1-69:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.69

Abstract

We study a variant of the generalized assignment problem (GAP) with group constraints. An instance of (Group GAP) is a set I of items, partitioned into L groups, and a set of m uniform (unit-sized) bins. Each item i in I has a size s_i >0, and a profit p_{i,j} >= 0 if packed in bin j. A group of items is satisfied if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total profit from satisfied groups is maximized. We point to central applications of Group GAP in Video-on-Demand services, mobile Device-to-Device network caching and base station cooperation in 5G networks.
Our main result is a 1/6-approximation algorithm for Group GAP instances where the total size of each group is at most m/2. At the heart of our algorithm lies an interesting derivation of a submodular function from the classic LP formulation of GAP, which facilitates the construction of a high profit solution utilizing at most half the total bin capacity, while the other half is reserved for later use. In particular, we give an algorithm for submodular maximization subject to a knapsack constraint, which finds a solution of profit at least 1/3 of the optimum, using at most half the knapsack capacity, under mild restrictions on element sizes. Our novel approach of submodular optimization subject to a knapsack with reserved capacity constraint may find applications in solving other group assignment problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Submodular optimization and polymatroids
  • Mathematics of computing → Linear programming
  • Mathematics of computing → Approximation algorithms
Keywords
  • Group Generalized Assignment Problem
  • Submodular Maximization
  • Knapsack Constraints
  • Approximation Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ron Adany, Moran Feldman, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, Hadas Shachnai, and Tami Tamir. All-Or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns. ACM Trans. Algorithms, 12(3):38:1-38:25, 2016. Google Scholar
  2. V. Balachandran. An Integer Generalized Transportation Model for Optimal Job Assignment in Computer Networks. Operations Research, 24(4):742-759, 1976. Google Scholar
  3. Amotz Bar-Noy and George Rabanca. Tight approximation bounds for the seminar assignment problem. In International Workshop on Approximation and Online Algorithms, pages 170-182. Springer, 2016. Google Scholar
  4. Marco Bender, Clemens Thielen, and Stephan Westphal. Packing items into several bins facilitates approximating the separable assignment problem. Inf. Processing Letters, 115(6-8):570-575, 2015. Google Scholar
  5. Niv Buchbinder and Moran Feldman. Deterministic Algorithms for Submodular Maximization Problems. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 392-403, 2016. Google Scholar
  6. Niv Buchbinder and Moran Feldman. Submodular Functions Maximization Problems - A Survey. In Teofilo F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics (2nd Edition), volume 1, chapter 42. Chapman and Hall/CRC, 2018. Google Scholar
  7. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a Monotone Submodular Function Subject to a Matroid Constraint. SIAM J. on Computing, 40(6):1740-1766, 2011. Google Scholar
  8. C. Chekuri and S. Khanna. A PTAS for the Multiple Knapsack Problem. SIAM J. on Computing, 35(3):713-728, 2006. Google Scholar
  9. Lin Chen and Guochuan Zhang. Packing Groups of Items into Multiple Knapsacks. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 28:1-28:13, 2016. Google Scholar
  10. Robert G. Cromley and Dean M. Hanink. Coupling land use allocation models with raster GIS. Journal of Geographical Systems, 1(2):137-153, 1999. Google Scholar
  11. Uriel Feige. A Threshold of ln n for Approximating Set Cover. J. ACM, 45(4), July 1998. Google Scholar
  12. Uriel Feige and Jan Vondrák. Approximation algorithms for allocation problems: Improving the factor of 1-1/e. In 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS'06, pages 667-676, 2006. Google Scholar
  13. M. Feldman, J. Naor, and R. Schwartz. A Unified Continuous Greedy Algorithm for Submodular Maximization. In 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS'11, pages 570-579, 2011. Google Scholar
  14. Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. Tight Approximation Algorithms for Maximum Separable Assignment Problems. Math. Oper. Res., 36(3):416-431, 2011. Google Scholar
  15. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  16. Ariel Kulik, Kanthi K. Sarpatwar, Baruch Schieber, and Hadas Shachnai. Generalized Assignment via Submodular Optimization with Reserved Capacity. CoRR, abs/1907.01745, 2019. URL: http://arxiv.org/abs/1907.01745.
  17. Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization, volume 46. Cambridge University Press, 2011. Google Scholar
  18. Hui Lin and Jeff Bilmes. Multi-document Summarization via Budgeted Maximization of Submodular Functions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, HLT'10, 2010. Google Scholar
  19. G. L. Nemhauser and L. A. Wolsey. Best Algorithms for Approximating the Maximum of a Submodular Set Function. Math. Oper. Res., 3(3):177-188, 1978. Google Scholar
  20. Kanthi K. Sarpatwar, Baruch Schieber, and Hadas Shachnai. Generalized Assignment of Time-Sensitive Item Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 24:1-24:18, 2018. Google Scholar
  21. David B. Shmoys and Éva Tardos. An approximation algorithm for the generalized assignment problem. Math. Program., 62:461-474, 1993. Google Scholar
  22. Maxim Sviridenko. A Note on Maximizing a Submodular Set Function Subject to Knapsack Constraint. Operations Research Letters, 32:41-43, 2004. Google Scholar
  23. Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In 40th Annual ACM Symposium on Theory of Computing, STOC, Victoria, British Columbia, Canada, May 17-20, 2008, pages 67-74, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact