کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5128398 | 1378595 | 2016 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A logarithmic approximation for polymatroid congestion games
ترجمه فارسی عنوان
یک تقسیم لگاریتمی برای بازی های احتمالی پلیموتید
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We study the problem of computing a social optimum in polymatroid congestion games, where the strategy space of every player consists of a player-specific integral polymatroid base polyhedron on a set of resources. For non-decreasing cost functions we devise an HÏ-approximation algorithm, where Ï is the sum of the ranks of the polymatroids and HÏ denotes the Ï-th harmonic number. The approximation guarantee is best possible up to a constant factor and solves an open problem of Ackermann et al. (2008).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 44, Issue 6, November 2016, Pages 712-717
Journal: Operations Research Letters - Volume 44, Issue 6, November 2016, Pages 712-717
نویسندگان
Tobias Harks, Tim Oosterwijk, Tjark Vredeveld,