کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141686 | 957082 | 2013 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximating the least core value and least core of cooperative games with supermodular costs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Approximating the least core value and least core of cooperative games with supermodular costs Approximating the least core value and least core of cooperative games with supermodular costs](/preview/png/1141686.png)
چکیده انگلیسی
We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a 3-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time algorithm for computing a cost allocation in the 2-approximate least core of these games. This approximation framework extends naturally to submodular profit cooperative games. For scheduling games, a special class of supermodular cost cooperative games, we give a fully polynomial-time approximation scheme for computing the least core value. For matroid profit games, a special class of submodular profit cooperative games, we give exact polynomial-time algorithms for computing the least core value as well as a least core cost allocation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 10, Issue 2, May 2013, Pages 163-180
Journal: Discrete Optimization - Volume 10, Issue 2, May 2013, Pages 163-180
نویسندگان
Andreas S. Schulz, Nelson A. Uhan,