دورية أكاديمية
Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
| العنوان: | Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees |
|---|---|
| المؤلفون: | Khaled Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://drops.dagstuhl.de/opus/volltexte/2012/3865/pdf/26.pdfTest. |
| المجموعة: | CiteSeerX |
| مصطلحات موضوعية: | Integer Decomposition, Linear Programming, Scheduling, Unsplittable Flows Digital Object Identifier 10.4230/LIPIcs.FSTTCS.2012.267 |
| الوصف: | We study the Unsplittable Flow Problem (UFP) and related variants, namely UFP with Bag Constraints and UFP with Rounds, on paths and trees. We provide improved constant factor approximation algorithms for all these problems under the no bottleneck assumption (NBA), which says that the maximum demand for any source-sink pair is at most the minimum capacity of any edge. We obtain these improved results by expressing a feasible solution to a natural LP relaxation of the UFP as a near-convex combination of feasible integral solutions. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| العلاقة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.402.7882Test; http://drops.dagstuhl.de/opus/volltexte/2012/3865/pdf/26.pdfTest |
| الإتاحة: | http://drops.dagstuhl.de/opus/volltexte/2012/3865/pdf/26.pdfTest |
| حقوق: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.D3D5C532 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |