التفاصيل البيبلوغرافية
| العنوان: |
Minimum latency submodular cover |
| المؤلفون: |
Zwaan, GRJ Ruben van der, Im, S, Nagarajan, V |
| بيانات النشر: |
Springer |
| سنة النشر: |
2012 |
| المجموعة: |
Eindhoven University of Technology (TU/e): Research Portal |
| الوصف: |
We study the submodular ranking problem in the presence of metric costs. The input to the minimum latency submodular cover (MLSC ) problem consists of a metric (V,d) with source r¿¿¿V and m monotone submodular functions f 1, f 2, ., f m : 2 V ¿¿¿[0,1]. The goal is to find a path originating at r that minimizes the total cover time of all functions; the cover time of function f i is the smallest value t such that f i has value one for the vertices visited within distance t along the path. This generalizes many previously studied problems, such as submodular ranking [1] when the metric is uniform, and group Steiner tree [14] when m¿=¿1 and f 1 is a coverage function. We give a polynomial time O(log1¿·log2+d|V|) -approximation algorithm for MLSC, where e¿>¿0 is the smallest non-zero marginal increase of any {fi}mi=1 and d¿>¿0 is any constant. This result is enabled by a simpler analysis of the submodular ranking algorithm from [1]. We also consider the stochastic submodular ranking problem where elements V have random instantiations, and obtain an adaptive algorithm with an O(log1/ e) approximation ratio, which is best possible. This result also generalizes several previously studied stochastic problems, eg. adaptive set cover [15] and shared filter evaluation [24,23]. |
| نوع الوثيقة: |
other/unknown material |
| وصف الملف: |
application/pdf |
| اللغة: |
English |
| العلاقة: |
http://repository.tue.nl/758018Test |
| الإتاحة: |
http://repository.tue.nl/758018Test |
| حقوق: |
Copyright (c) Zwaan, GRJ Ruben van der ; Copyright (c) Im, S ; Copyright (c) Nagarajan, V |
| رقم الانضمام: |
edsbas.6A3D02A8 |
| قاعدة البيانات: |
BASE |
