Packing arborescences in directed graphs is a central concept in combinatorial optimization. A seminal work of Edmonds (1973) presents a min-max (duality) relation between maximum r-arborescence packing and minimum r-cut (a cut that separates some vertex from the root r). Quite a few researchers (Frank (1978), Cai (1983), and Kamiyama, Katoh, and Takizawa (2009)) have generalized Edmonds’ min-max result to characterize packings of arborescences at multiple roots. Nonetheless, these min-max relations, unlike Edmonds’ result, cannot be seen as linear programming (LP) duality between cuts and packings. In this paper, we initiate the study of two min-max relations of multi-commodity arborescence packings based on the LP duality view. We show tight relations between fractional arborescence packings and cuts as well as efficient algorithms that achieve such ratios. Our cut problems are natural and rich in modeling power, e.g., they capture cornerstone optimization problems such as set cover, densest sub (hyper) graphs. Therefore, our algorithmic results generalize and subsume quite a few existing algorithms. Our techniques are based on a simple and illustrative primal-dual analysis, that allows us to reduce the task of upper bounding the min-max ratios for our problems to that of set covering problems. As a bonus, these techniques offer new primal-dual insights to the original result of Edmonds and Kamiyama, Katoh and Takizawa.

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

Approximate Cut & Packing Ratios for Multi-commodity Arborescences

  • Parinya Chalermsook,
  • Chien-Chung Huang

摘要

Packing arborescences in directed graphs is a central concept in combinatorial optimization. A seminal work of Edmonds (1973) presents a min-max (duality) relation between maximum r-arborescence packing and minimum r-cut (a cut that separates some vertex from the root r). Quite a few researchers (Frank (1978), Cai (1983), and Kamiyama, Katoh, and Takizawa (2009)) have generalized Edmonds’ min-max result to characterize packings of arborescences at multiple roots. Nonetheless, these min-max relations, unlike Edmonds’ result, cannot be seen as linear programming (LP) duality between cuts and packings. In this paper, we initiate the study of two min-max relations of multi-commodity arborescence packings based on the LP duality view. We show tight relations between fractional arborescence packings and cuts as well as efficient algorithms that achieve such ratios. Our cut problems are natural and rich in modeling power, e.g., they capture cornerstone optimization problems such as set cover, densest sub (hyper) graphs. Therefore, our algorithmic results generalize and subsume quite a few existing algorithms. Our techniques are based on a simple and illustrative primal-dual analysis, that allows us to reduce the task of upper bounding the min-max ratios for our problems to that of set covering problems. As a bonus, these techniques offer new primal-dual insights to the original result of Edmonds and Kamiyama, Katoh and Takizawa.