Integer plane multiflow maximisation: one-quarter-approximation and gaps

• 成果类型: Article
• 署名作者: Garg, Naveen; Kumar, Nikhil; Sebo, Andras
• 署名单位: Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Potsdam; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01700-8
• 发表日期: 2022
• 页码: 403-419
• 关键词: multicommodity flows; algorithms; multicut; paths; ratio

摘要

In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-multicut-gap. We consider instances where the union of the supply and demand graphs is planar and prove that there exists a multiflow of value at least half the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer flow of value at least half the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing at most half the value thus providing a 1/4-approximation algorithm and integrality gap for maximum integer multiflows in the plane.