On fixed cost k-flow problems

Mohammadtaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


In the Fixed Cost k -Flow problem, we are given a graph G = (V,E) with edge-capacities {u e |e ∈E} and edge-costs {c e |e ∈E}, source-sink pair s,t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. We show that Group Steiner is a special case of Fixed Cost k -Flow, thus obtaining the first polylogarithmic lower bound for the problem; this also implies the first non constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k -Flow. In the Bipartite Fixed-Cost k -Flow problem, we are given a bipartite graph G = (A ∪ B,E) and an integer k > 0. The goal is to find a node subset S ⊆ A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an O(√k log k) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V,E) with edge-costs and integer charges {b v :v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [10]. Besides that, it generalizes many problems such as Steiner Forest, k -Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log3+ε n approximation scheme for it using Group Steiner techniques.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفApproximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers
ناشرSpringer Verlag
عدد الصفحات12
رقم المعيار الدولي للكتب (المطبوع)9783319080000
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2014
الحدث11th International Workshop on Approximation and Online Algorithms, WAOA 2013 - Sophia Antipolis, فرنسا
المدة: ٥ سبتمبر ٢٠١٣٦ سبتمبر ٢٠١٣

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت8447 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference11th International Workshop on Approximation and Online Algorithms, WAOA 2013
المدينةSophia Antipolis


أدرس بدقة موضوعات البحث “On fixed cost k-flow problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا