Document Open Access Logo

Budgeted Out-Tree Maximization with Submodular Prizes

Authors Gianlorenzo D'Angelo , Esmaeil Delfaraz, Hugo Gilbert

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.9.pdf
  • Filesize: 0.78 MB
  • 19 pages

Document Identifiers

Author Details

Gianlorenzo D'Angelo
  • Gran Sasso Science Institute, L'Aquila, Italy
Esmaeil Delfaraz
  • Gran Sasso Science Institute, L'Aquila, Italy
Hugo Gilbert
  • Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, 75016 Paris, France

Funding

  • D'Angelo, Gianlorenzo: Partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Markets".

Cite AsGet BibTex

Gianlorenzo D'Angelo, Esmaeil Delfaraz, and Hugo Gilbert. Budgeted Out-Tree Maximization with Submodular Prizes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.9

Abstract

We consider a variant of the prize collecting Steiner tree problem in which we are given a directed graph D = (V,A), a monotone submodular prize function p:2^V → ℝ^+ ∪ {0}, a cost function c:V → ℤ^+, a root vertex r ∈ V, and a budget B. The aim is to find an out-subtree T of D rooted at r that costs at most B and maximizes the prize function. We call this problem Directed Rooted Submodular Tree (DRST). For the case of undirected graphs and additive prize functions, Moss and Rabani [SIAM J. Comput. 2007] gave an algorithm that guarantees an O(log|V|)-approximation factor if a violation by a factor 2 of the budget constraint is allowed. Bateni et al. [SIAM J. Comput. 2018] improved the budget violation factor to 1+ε at the cost of an additional approximation factor of O(1/ε²), for any ε ∈ (0,1]. For directed graphs, Ghuge and Nagarajan [SODA 2020] gave an optimal quasi-polynomial time O({log n'}/{log log n'})-approximation algorithm, where n' is the number of vertices in an optimal solution, for the case in which the costs are associated to the edges. In this paper, we give a polynomial time algorithm for DRST that guarantees an approximation factor of O(√B/ε³) at the cost of a budget violation of a factor 1+ε, for any ε ∈ (0,1]. The same result holds for the edge-cost case, to the best of our knowledge this is the first polynomial time approximation algorithm for this case. We further show that the unrooted version of DRST can be approximated to a factor of O(√B) without budget violation, which is an improvement over the factor O(Δ √B) given in [Kuo et al. IEEE/ACM Trans. Netw. 2015] for the undirected and unrooted case, where Δ is the maximum degree of the graph. Finally, we provide some new/improved approximation bounds for several related problems, including the additive-prize version of DRST, the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Prize Collecting Steiner Tree
  • Directed graphs
  • Approximation Algorithms
  • Budgeted Problem

Metrics

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

Related Versions

References

  1. Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Howard J. Karloff. Improved approximation algorithms for prize-collecting steiner tree and TSP. SIAM J. Comput., 40(2):309-332, 2011. Google Scholar
  2. Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, and Vahid Liaghat. Improved approximation algorithms for (budgeted) node-weighted steiner problems. SIAM J. Comput., 47(4):1275-1293, 2018. Google Scholar
  3. Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed steiner problems. J. Algorithms, 33(1):73-91, 1999. Google Scholar
  4. Xuefeng Chen, Xin Cao, Yifeng Zeng, Yixiang Fang, and Bin Yao. Optimal region search with submodular maximization. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI, pages 1216-1222, 2020. Google Scholar
  5. Xiuzhen Cheng, Yingshu Li, Ding-Zhu Du, and Hung Q Ngo. Steiner trees in industry. In Handbook of combinatorial optimization, pages 193-216. Springer, 2004. Google Scholar
  6. Gianlorenzo D'Angelo, Esmaeil Delfaraz, and Hugo Gilbert. Budgeted out-tree maximization with submodular prizes. CoRR, abs/2204.12162, 2022. Google Scholar
  7. Kiril Danilchenko, Michael Segal, and Zeev Nutov. Covering users by a connected swarm efficiently. In Algorithms for Sensor Systems - 16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2020, , Revised Selected Papers, volume 12503 of Lecture Notes in Computer Science, pages 32-44. Springer, 2020. Google Scholar
  8. Xiaofeng Gao, Junwei Lu, Haotian Wang, Fan Wu, and Guihai Chen. Algorithm design and analysis for wireless relay network deployment problem. IEEE Trans. Mob. Comput., 18(10):2257-2269, 2019. Google Scholar
  9. N Garg. A 3 factor approximation algorithm for the minimum tree spanning k vertices. In Proc of 37th Symp. on Foundations of Computer Science, pages 302-309, 1996. Google Scholar
  10. Naveen Garg. Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 396-402. ACM, 2005. Google Scholar
  11. Rohan Ghuge and Viswanath Nagarajan. Quasi-polynomial algorithms for submodular tree orienteering and other directed network design problems. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1039-1048. SIAM, 2020. Google Scholar
  12. Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296-317, 1995. Google Scholar
  13. Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li. O(log^2k/log log k)-approximation algorithm for directed steiner tree: A tight quasi-polynomial-time algorithm. CoRR, abs/1811.03020, 2018. Google Scholar
  14. Sudipto Guha, Anna Moss, Joseph Naor, and Baruch Schieber. Efficient recovery from power outage (extended abstract). In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 574-582. ACM, 1999. Google Scholar
  15. Dorit S. Hochbaum and Xu Rao. Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer. Inf. Process. Lett., 158:105940, 2020. Google Scholar
  16. Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa. Maximizing covered area in the euclidean plane with connectivity constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, volume 145 of LIPIcs, pages 32:1-32:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  17. Lingxiao Huang, Jian Li, and Qicai Shi. Approximation algorithms for the connected sensor cover problem. Theor. Comput. Sci., 809:563-574, 2020. Google Scholar
  18. David S. Johnson, Maria Minkoff, and Steven Phillips. The prize collecting steiner tree problem: theory and practice. In David B. Shmoys, editor, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 760-769. ACM/SIAM, 2000. Google Scholar
  19. Samir Khuller, Manish Purohit, and Kanthi K. Sarpatwar. Analyzing the optimal neighborhood: Algorithms for partial and budgeted connected dominating set problems. SIAM J. Discret. Math., 34(1):251-270, 2020. Google Scholar
  20. Philip N. Klein and R. Ravi. A nearly best-possible approximation algorithm for node-weighted steiner trees. J. Algorithms, 19(1):104-115, 1995. Google Scholar
  21. Jochen Könemann, Sina Sadeghian Sadeghabad, and Laura Sanità. An LMP o(log n)-approximation algorithm for node weighted prize collecting steiner tree. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 568-577. IEEE Computer Society, 2013. Google Scholar
  22. Guy Kortsarz and Zeev Nutov. Approximating some network design problems with node costs. Theor. Comput. Sci., 412(35):4482-4492, 2011. Google Scholar
  23. Tung-Wei Kuo, Kate Ching-Ju Lin, and Ming-Jer Tsai. Maximizing submodular set function with connectivity constraint: Theory and application to networks. IEEE/ACM Trans. Netw., 23(2):533-546, 2015. Google Scholar
  24. Ioannis Lamprou, Ioannis Sigalas, and Vassilis Zissimopoulos. Improved budgeted connected domination and budgeted edge-vertex domination. Theor. Comput. Sci., 858:1-12, 2021. Google Scholar
  25. Heungsoon Felix Lee and Daniel R Dooly. Algorithms for the constrained maximum-weight connected graph problem. Naval Research Logistics (NRL), 43(7):985-1008, 1996. Google Scholar
  26. Shi Li and Bundit Laekhanukit. Polynomial integrality gap of flow LP for directed steiner tree. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 3230-3236. SIAM, 2022. Google Scholar
  27. Anna Moss and Yuval Rabani. Approximation algorithms for constrained node weighted steiner tree problems. SIAM J. Comput., 37(2):460-481, 2007. Google Scholar
  28. George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions - I. Math. Program., 14(1):265-294, 1978. Google Scholar
  29. Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, and David P. Williamson. Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Math. Oper. Res., 45(2):576-590, 2020. Google Scholar
  30. Yingli Ran, Zhao Zhang, Ker-I Ko, and Jun Liang. An approximation algorithm for maximum weight budgeted connected set cover. J. Comb. Optim., 31(4):1505-1517, 2016. Google Scholar
  31. Stephan Seufert, Srikanta J. Bedathur, Julián Mestre, and Gerhard Weikum. Bonsai: Growing interesting small trees. In Geoffrey I. Webb, Bing Liu, Chengqi Zhang, Dimitrios Gunopulos, and Xindong Wu, editors, ICDM 2010, The 10th IEEE International Conference on Data Mining, pages 1013-1018. IEEE Computer Society, 2010. Google Scholar
  32. Fabio Vandin, Eli Upfal, and Benjamin J. Raphael. Algorithms for detecting significantly mutated pathways in cancer. J. Comput. Biol., 18(3):507-522, 2011. Google Scholar
  33. Wenzheng Xu, Yueying Sun, Rui Zou, Weifa Liang, Qiufen Xia, Feng Shan, Tian Wang, Xiaohua Jia, and Zheng Li. Throughput maximization of UAV networks. IEEE/ACM Transactions on Networking, 30(2):881-895, 2022. URL: https://doi.org/10.1109/TNET.2021.3125982.
  34. Nan Yu, Haipeng Dai, Guihai Chen, Alex X. Liu, Bingchuan Tian, and Tian He. Connectivity-constrained placement of wireless chargers. IEEE Trans. Mob. Comput., 20(3):909-927, 2021. Google Scholar
  35. Alexander Zelikovsky. A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica, 18(1):99-110, 1997. Google Scholar
  36. Chenyang Zhou, Anisha Mazumder, Arun Das, Kaustav Basu, Navid Matin-Moghaddam, Saharnaz Mehrani, and Arunabha Sen. Relay node placement under budget constraint. In Paolo Bellavista and Vijay K. Garg, editors, Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN, pages 35:1-35:11. ACM, 2018. 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 Imprint Privacy Contact