ملخص
In the Steiner κ-Forest problem we are given an edge weighted graph, a collection D of node pairs, and an integer κ ≤ |D|. The goal is to find a minimum cost subgraph that connects at least κ pairs. The best known ratio for this problem is min{O( √n),O(√κ)} [8]. In [8] it is also shown that ratio ρ for Steiner κ-Forest implies ratio O(ρ · log2 n) for the Dial-a-Ride problem: given an edge weighted graph and a set of items with a source and a destination each, find a minimum length tour to move each object from its source to destination, but carrying at most κ objects at a time. The only other algorithm known for Dial-a-Ride, besides the one resulting from [8], has ratio O( √n) [4]. We obtain ratio n0.448 for Steiner κ-Forest and Dial-a-Ride with unit weights, breaking the O(√n) ratio barrier for this natural special case. We also show that if the maximum weight of an edge is O(nε), then one can achieve ratio O(n(1+ε)·0.448), which is less than √n if ε is small enough. To prove our main result we consider the following generalization of the Minimum κ-Edge Subgraph (Mk-ES) problem, which we call Min-Cost ℓ-Edge-Profit Subgraph (MCℓ-EPS): Given a graph G = (V,E) with edge-profits p = {pe : e ∈ E} and node-costs c = {cv : v ∈ V }, and a lower profit bound ℓ, find a minimum node-cost subgraph of G of edge profit at least ℓ. The Mk-ES problem is a special case of MCℓ-EPS with unit node costs and unit edge profits. The currently best known ratio for Mk-ES is n3-2√2+ε (note that 3-2√2 < 0.1716) [5]. We extend this ratio to MCℓ-EPS for arbitrary node weights and edge profits that are polynomial in n, which may be of independent interest.
اللغة الأصلية | الإنجليزيّة |
---|---|
عنوان منشور المضيف | Leibniz International Proceedings in Informatics, LIPIcs |
المحررون | Klaus Jansen, Jose D. P. Rolim, Nikhil R. Devanur, Cristopher Moore |
ناشر | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
الصفحات | 115-127 |
عدد الصفحات | 13 |
رقم المعيار الدولي للكتب (الإلكتروني) | 9783939897743 |
المعرِّفات الرقمية للأشياء | |
حالة النشر | نُشِر - 1 سبتمبر 2014 |
الحدث | 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 - Barcelona, أسبانيا المدة: ٤ سبتمبر ٢٠١٤ → ٦ سبتمبر ٢٠١٤ |
سلسلة المنشورات
الاسم | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
مستوى الصوت | 28 |
رقم المعيار الدولي للدوريات (المطبوع) | 1868-8969 |
!!Conference
!!Conference | 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 |
---|---|
الدولة/الإقليم | أسبانيا |
المدينة | Barcelona |
المدة | ٤/٠٩/١٤ → ٦/٠٩/١٤ |
ملاحظة ببليوغرافية
Publisher Copyright:© Michael Dinitz, Guy Kortsarz, and Zeev Nutov.