Constrained forest problems form a class of graph problems where specific connectivity requirements for certain cuts within the graph must be satisfied by selecting the minimum-cost set of edges. The prize-collecting version of these problems introduces flexibility by allowing penalties to be paid to ignore some connectivity requirements. Goemans and Williamson [8] introduced a general technique and developed a 2-approximation algorithm for constrained forest problems. Further, Sharma, Swamy, and Williamson [16] extended this work by developing a 2.54-approximation algorithm for the prize-collecting version of these problems. Motivated by the generality of their framework, which includes problems such as Steiner trees, Steiner forests, and their variants, we pursued further exploration. We present a significant improvement by achieving a 2-approximation algorithm for this general model, matching the approximation factor of the constrained forest problems. Notably, the best-known approximation factor for a specific case, the Steiner forest, has remained at 2 since it was established in 1991 by Agrawal, Klein, and Ravi [1].

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Prize-Collecting Forest with Submodular Penalties: Improved Approximation

  • Ali Ahmadi,
  • Iman Gholami,
  • MohammadTaghi Hajiaghayi,
  • Peyman Jabbarzade,
  • Mohammad Mahdavi

摘要

Constrained forest problems form a class of graph problems where specific connectivity requirements for certain cuts within the graph must be satisfied by selecting the minimum-cost set of edges. The prize-collecting version of these problems introduces flexibility by allowing penalties to be paid to ignore some connectivity requirements. Goemans and Williamson [8] introduced a general technique and developed a 2-approximation algorithm for constrained forest problems. Further, Sharma, Swamy, and Williamson [16] extended this work by developing a 2.54-approximation algorithm for the prize-collecting version of these problems. Motivated by the generality of their framework, which includes problems such as Steiner trees, Steiner forests, and their variants, we pursued further exploration. We present a significant improvement by achieving a 2-approximation algorithm for this general model, matching the approximation factor of the constrained forest problems. Notably, the best-known approximation factor for a specific case, the Steiner forest, has remained at 2 since it was established in 1991 by Agrawal, Klein, and Ravi [1].