کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141750 | 957088 | 2012 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The best choice problem for upward directed graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The best choice problem for upward directed graphs The best choice problem for upward directed graphs](/preview/png/1141750.png)
چکیده انگلیسی
We consider a generalization of the best choice problem to upward directed graphs. We describe a strategy for choosing a maximal element (i.e., an element with no outgoing edges) when a selector knows in advance only the number nn of vertices of the graph. We show that, as long as the number of elements dominated directly by the maximal ones is not greater than c1n for some positive constant c1c1 and the indegree of remaining vertices is bounded by a constant DD, the probability pnpn of the right choice according to our strategy satisfies lim infn→∞pnn≥δ>0, where δδ is a constant depending on c1c1 and DD.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 9, Issue 3, August 2012, Pages 200–204
Journal: Discrete Optimization - Volume 9, Issue 3, August 2012, Pages 200–204
نویسندگان
Małgorzata Sulkowska,