log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
2-Approximation for Prize-Collecting Steiner Forest
Ali, Iman, Peyman, and Mohammad - University of Maryland, College Park
IRB 4105 or Zoom: https://umd.zoom.us/j/6778156199?pwd=NkJKZG1Ib2Jxbmd5ZzNrVVlNMm91QT09
Friday, September 22, 2023, 10:00-11:00 am Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract
Approximation algorithms for the prize-collecting Steiner forest problem (PCSF) have been a subject of research for over three decades, starting with the seminal works of Agrawal, Klein, and Ravi and Goemans and Williamson on Steiner forest and prize-collecting problems. In this paper, we propose and analyze a natural deterministic algorithm for PCSF that achieves a 2-approximate solution in polynomial time. This represents a significant improvement compared to the previously best known algorithm with a 2.54-approximation factor developed by Hajiaghayi and Jain in 2006. Furthermore, Könemann, Olver, Pashkovich, Ravi, Swamy, and Vygen have established an integrality gap of at least 9/4 for the natural LP relaxation for PCSF. However, we surpass this gap through the utilization of a combinatorial algorithm and a novel analysis technique. Since 2 is the best known approximation guarantee for Steiner forest problem, which is a special case of PCSF, our result matches this factor and closes the gap between the Steiner forest problem and its generalized version, PCSF.
 
Bio

Ali, Iman, Peyman, and Mohammad are second-year PhD students at the University of Maryland, College Park, advised by MohammadTaghi Hajiaghayi. Their research interests primarily lie in algorithmic graph theory and approximation algorithms. 

This talk is organized by Kishen N Gowda