Document Open Access Logo

Budget-Smoothed Analysis for Submodular Maximization

Authors Aviad Rubinstein, Junyao Zhao

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.113.pdf
  • Filesize: 0.84 MB
  • 23 pages

Document Identifiers

Author Details

Aviad Rubinstein
  • Computer Science Department, Stanford University, CA, USA
Junyao Zhao
  • Computer Science Department, Stanford University, CA, USA

Funding

  • Rubinstein, Aviad: Supported by NSF CCF-1954927, and a David and Lucile Packard Fellowship.
  • Zhao, Junyao: Supported by NSF CCF-1954927.

Acknowledgements

We thank Eric Balkanski and Matt Weinberg for interesting discussions and comments on earlier drafts.

Cite AsGet BibTex

Aviad Rubinstein and Junyao Zhao. Budget-Smoothed Analysis for Submodular Maximization. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 113:1-113:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.113

Abstract

The greedy algorithm for monotone submodular function maximization subject to cardinality constraint is guaranteed to approximate the optimal solution to within a 1-1/e factor. Although it is well known that this guarantee is essentially tight in the worst case - for greedy and in fact any efficient algorithm, experiments show that greedy performs better in practice. We observe that for many applications in practice, the empirical distribution of the budgets (i.e., cardinality constraints) is supported on a wide range, and moreover, all the existing hardness results in theory break under a large perturbation of the budget. To understand the effect of the budget from both algorithmic and hardness perspectives, we introduce a new notion of budget-smoothed analysis. We prove that greedy is optimal for every budget distribution, and we give a characterization for the worst-case submodular functions. Based on these results, we show that on the algorithmic side, under realistic budget distributions, greedy and related algorithms enjoy provably better approximation guarantees, that hold even for worst-case functions, and on the hardness side, there exist hard functions that are fairly robust to all the budget distributions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Submodular optimization and polymatroids
Keywords
  • Submodular optimization
  • Beyond worst-case analysis
  • Greedy algorithms
  • Hardness of approximation

Metrics

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

Related Versions

References

  1. Sarah Almukhtar, Thomas Kaplan, and Rachel Shorey. 2020 democrats went on a spending spree in the final months of 2019. https://www.nytimes.com/interactive/2020/02/01/us/elections/democratic-q4-fundraising.html, 2020.
  2. Georgios Amanatidis, Pieter Kleer, and Guido Schäfer. Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 901-919, 2019. URL: https://doi.org/10.1145/3328526.3329622.
  3. Nima Anari, Gagan Goel, and Afshin Nikzad. Budget feasible procurement auctions. Operations Research, 66(3):637-652, 2018. Google Scholar
  4. Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, and Tim Roughgarden. Sketching valuation functions. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1025-1035, 2012. URL: https://doi.org/10.1137/1.9781611973099.81.
  5. Ashwinkumar Badanidiyuru, Robert Kleinberg, and Yaron Singer. Learning on a budget: posted price mechanisms for online procurement. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012, pages 128-145, 2012. URL: https://doi.org/10.1145/2229012.2229026.
  6. Maria-Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. Learning valuation functions. In COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, pages 4.1-4.24, 2012. URL: http://proceedings.mlr.press/v23/balcan12b/balcan12b.pdf.
  7. Eric Balkanski and Jason D. Hartline. Bayesian budget feasibility with posted pricing. In Proceedings of the 25th International Conference on World Wide Web, WWW 2016, Montreal, Canada, April 11 - 15, 2016, pages 189-203, 2016. URL: https://doi.org/10.1145/2872427.2883032.
  8. Eric Balkanski, Sharon Qian, and Yaron Singer. Instance specific approximations for submodular maximization. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 609-618. PMLR, 2021. Google Scholar
  9. Eric Balkanski, Aviad Rubinstein, and Yaron Singer. The power of optimization from samples. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 4017-4025, 2016. URL: http://papers.nips.cc/paper/6447-the-power-of-optimization-from-samples.
  10. Hau Chan and Jing Chen. Truthful multi-unit procurements with budgets. In Web and Internet Economics - 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings, pages 89-105, 2014. URL: https://doi.org/10.1007/978-3-319-13129-0_7.
  11. Hau Chan and Jing Chen. Budget feasible mechanisms for dealers. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, Singapore, May 9-13, 2016, pages 113-122, 2016. URL: http://dl.acm.org/citation.cfm?id=2936945.
  12. Vaggos Chatziafratis, Tim Roughgarden, and Jan Vondrák. Stability and recovery for independence systems. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pages 26:1-26:15, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.26.
  13. Ning Chen, Nick Gravin, and Pinyan Lu. On the approximability of budget feasible mechanisms. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 685-699. Society for Industrial and Applied Mathematics, 2011. Google Scholar
  14. Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discret. Appl. Math., 7(3):251-274, 1984. URL: https://doi.org/10.1016/0166-218X(84)90003-9.
  15. Daniel Dadush and Sophie Huiberts. A friendly smoothed analysis of the simplex method. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 390-403. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188826.
  16. Abhimanyu Das and David Kempe. Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pages 1057-1064, 2011. Google Scholar
  17. Shahar Dobzinski, Christos H. Papadimitriou, and Yaron Singer. Mechanisms for complement-free procurement. In Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), San Jose, CA, USA, June 5-9, 2011, pages 273-282, 2011. URL: https://doi.org/10.1145/1993574.1993615.
  18. Ethan R Elenberg, Rajiv Khanna, Alexandros G Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity. The Annals of Statistics, 46(6B):3539-3568, 2018. Google Scholar
  19. Alina Ene and Huy L. Nguyen. A nearly-linear time algorithm for submodular maximization with a knapsack constraint. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 53:1-53:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.53.
  20. Ludwig Ensthaler and Thomas Giebe. A dynamic auction for multi-object procurement under a hard budget constraint. Research Policy, 43(1):179-189, 2014. Google Scholar
  21. Facebook. Facebook ad library report. https://www.facebook.com/ads/library/report/, 2020. Accessed: 2020-03-26.
  22. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  23. Vitaly Feldman and Pravesh Kothari. Learning coverage functions and private release of marginals. In Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, pages 679-702, 2014. URL: http://proceedings.mlr.press/v35/feldman14a.html.
  24. Gagan Goel, Afshin Nikzad, and Adish Singla. Mechanism design for crowdsourcing markets with heterogeneous tasks. In Proceedings of the Seconf AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2014, November 2-4, 2014, Pittsburgh, Pennsylvania, USA, 2014. URL: http://www.aaai.org/ocs/index.php/HCOMP/HCOMP14/paper/view/8968.
  25. Nick Gravin, Yaonan Jin, Pinyan Lu, and Chenhao Zhang. Optimal budget-feasible mechanisms for additive valuations. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 887-900. ACM, 2019. Google Scholar
  26. Rishi Gupta, Tim Roughgarden, and C. Seshadhri. Decompositions of triangle-dense graphs. SIAM J. Comput., 45(2):197-215, 2016. URL: https://doi.org/10.1137/140955331.
  27. Avinatan Hassidim and Yaron Singer. Submodular optimization under noise. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 1069-1122, 2017. URL: http://proceedings.mlr.press/v65/hassidim17a.html.
  28. Thibaut Horel, Stratis Ioannidis, and S. Muthukrishnan. Budget feasible mechanisms for experimental design. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings, pages 719-730, 2014. URL: https://doi.org/10.1007/978-3-642-54423-1_62.
  29. Thibaut Horel and Yaron Singer. Maximization of approximately submodular functions. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3045-3053, 2016. URL: http://papers.nips.cc/paper/6236-maximization-of-approximately-submodular-functions.
  30. David Kempe, Jon M. Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. Theory of Computing, 11:105-147, 2015. URL: https://doi.org/10.4086/toc.2015.v011a004.
  31. Pooya Jalaly Khalilabadi and Éva Tardos. Simple and efficient budget feasible mechanisms for monotone submodular valuations. In Web and Internet Economics - 14th International Conference, WINE 2018, Oxford, UK, December 15-17, 2018, Proceedings, pages 246-263, 2018. URL: https://doi.org/10.1007/978-3-030-04612-5_17.
  32. Sanjeev Khanna and Brendan Lucier. Influence maximization in undirected networks. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1482-1496, 2014. URL: https://doi.org/10.1137/1.9781611973402.109.
  33. Andreas Krause and Daniel Golovin. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems. Cambridge University Press, February 2014. Google Scholar
  34. Stefano Leonardi, Gianpiero Monaco, Piotr Sankowski, and Qiang Zhang. Budget feasible mechanisms on matroids. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 368-379, 2017. URL: https://doi.org/10.1007/978-3-319-59250-3_30.
  35. Juan Li, Yanmin Zhu, and Jiadi Yu. Redundancy-aware and budget-feasible incentive mechanism in crowd sensing. Comput. J., 63(1):66-79, 2020. URL: https://doi.org/10.1093/comjnl/bxy139.
  36. George L Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3):177-188, 1978. Google Scholar
  37. George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1):265-294, 1978. Google Scholar
  38. Besmira Nushi, Adish Singla, Andreas Krause, and Donald Kossmann. Learning and feature selection under budget constraints in crowdsourcing. In Proceedings of the Fourth AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2016, 30 October - 3 November, 2016, Austin, Texas, USA, pages 159-168, 2016. URL: http://aaai.org/ocs/index.php/HCOMP/HCOMP16/paper/view/14032.
  39. Zeev Nutov and Elad Shoham. Practical budgeted submodular maximization. CoRR, abs/2007.04937, 2020. URL: http://arxiv.org/abs/2007.04937.
  40. Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211-252, 2015. URL: https://doi.org/10.1007/s11263-015-0816-y.
  41. Grant Schoenebeck and Biaoshuai Tao. Influence maximization on undirected graphs: Towards closing the (1-1/e) gap. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 423-453, 2019. URL: https://doi.org/10.1145/3328526.3329650.
  42. Grant Schoenebeck, Biaoshuai Tao, and Fang-Yi Yu. Limitations of greed: Influence maximization in undirected networks re-visited. In AAMAS 2020, 2020. To appear. Google Scholar
  43. Yaron Singer. Budget feasible mechanisms. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 765-774. IEEE, 2010. Google Scholar
  44. Yaron Singer and Manas Mittal. Pricing mechanisms for crowdsourcing markets. In 22nd International World Wide Web Conference, WWW '13, Rio de Janeiro, Brazil, May 13-17, 2013, pages 1157-1166, 2013. URL: https://doi.org/10.1145/2488388.2488489.
  45. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385-463, 2004. URL: https://doi.org/10.1145/990308.990310.
  46. Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett., 32(1):41-43, 2004. URL: https://doi.org/10.1016/S0167-6377(03)00062-2.
  47. Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res., 42(4):1197-1218, 2017. URL: https://doi.org/10.1287/moor.2016.0842.
  48. Alfredo Torrico, Mohit Singh, and Sebastian Pokutta. On the unreasonable effectiveness of the greedy algorithm: Greedy adapts to sharpness. CoRR, abs/2002.04063, 2020. URL: http://arxiv.org/abs/2002.04063.
  49. Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM J. Comput., 42(1):265-304, 2013. URL: https://doi.org/10.1137/110832318.
  50. Duncan Watts and Steven Strogatz. Collective dynamics of ’small-world' networks. Nature, 1998. Google Scholar
  51. Yuichi Yoshida. Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint. CoRR, abs/1607.04527, 2016. URL: http://arxiv.org/abs/1607.04527.
  52. Dong Zhao, Xiang-Yang Li, and Huadong Ma. Budget-feasible online incentive mechanisms for crowdsourcing tasks truthfully. IEEE/ACM Trans. Netw., 24(2):647-661, 2016. URL: https://doi.org/10.1109/TNET.2014.2379281.
  53. Zhenzhe Zheng, Fan Wu, Xiaofeng Gao, Hongzi Zhu, Shaojie Tang, and Guihai Chen. A budget feasible incentive mechanism for weighted coverage maximization in mobile crowdsensing. IEEE Trans. Mob. Comput., 16(9):2392-2407, 2017. URL: https://doi.org/10.1109/TMC.2016.2632721.
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 Imprint Privacy Contact