پایان ترم الگوریتم پیشرفته

۱- از یک زمانبند حریصانه استفاده می‌کنیم. اگر زمان اجرای یک الگوریتم روی ۴ پردازنده ۲۶۰ ثانیه و روی ۳۲ پردازنده ۹۰ ثانیه باشد؛ آیا مقادیر T1=1024 و Tinfinity = 64 می‌توانند مقادیر معتبری باشند؟

۲-  الگوریتم push-relabel را روی گراف زیر اجرا کنید که همه‌ی یالهای آن وزن ۲ دارند به جز یال آخر که وزن ۱ دارد.

s->v1->....->vn->t

تعداد pushها و تعداد relabelها و زمان الگوریتم را حساب کنید.

۳- یک الگوریتم موازی برای محاسبه‌ی ترانهاده‌ی ماتریس X که n*n است بنویسید و کار و زمان و موازات آن را حساب کنید.

۴- یک شبکه شار داریم که یالهای آن آبی یا قرمز هستند. یالهای آبی ظرفیت ce دارند و یالهای قرمز کران پایین de دارند. شار بیشینه را می‌خواهیم به دست بیاوریم.

الف) برای آن یک LP بنویسید و ثابت کنید زمان آن خطی است.

ب) ثابت کنید اگر یالهای قرمز را بتوانیم خاموش و روشن کنیم؛ مسأله‌ی اینکه این گراف شار k دارد یا نه، np-complete است. (از subset-sum کمک بگیرید.)

۵- ثابت کنید دور فروشنده دوره‌گرد را نمی‌توان بهتر از یک تابع چندجمله‌ای بر حسب n تقریب زد.

۶- تابع پیشوندی در الگوریتم KMP را بنویسید و تحلیل کنید.

تمرین‌های الگوریتم پیشرفته

تمرین‌های کتاب که فقط شماره‌ی آنها داده شده بود. (این همه‌ی تمرین‌ها نیست)

Decentralized utilitarian mechanisms for scheduling games

http://www.sciencedirect.com/science/article/pii/S0899825613000560

Optimal Revenue-Sharing Double Auctions with Applications to Ad Exchanges

http://wwwconference.org/proceedings/www2014/proceedings/p19.pdf

Bicriteria Online Matching: Maximizing Weight and Cardinality

http://madalgo.au.dk/fileadmin/madalgo/OA_PDF_s/C312.pdf

Multiplicative Bidding in Online Advertising

http://arxiv.org/pdf/1404.6727.pdf

موضوعات کلی کارگاه نظریه الگوریتمی بازیها

http://en.wikipedia.org/wiki/Incentive_compatibility

http://en.wikipedia.org/wiki/Mechanism_design

http://en.wikipedia.org/wiki/Revelation_principle

http://en.wikipedia.org/wiki/Combinatorial_auction

http://en.wikipedia.org/wiki/Job_scheduling_game

http://en.wikipedia.org/wiki/Coordination_game

حل تمرین‌های سری اول نظریه الگوریتمی بازی‌ها

من این درس را نداشتم پس ممکن است جوابها درست نباشند!

۱- الف) تعادل نش وقتی است که هیچ کس نخواهد انتخاب خودش را عوض کند.

همه عدد ۱ را انتخاب کنند. در این صورت همه به ۲/۳*۱ نزدیک‌تر هستند. چون تقارن داریم همه باید مثل هم انتخاب کنند و تنها عددی که اگر همه انتخاب کنند کسی با انجام ندادن آن برنده نمی‌شود همین ۱ است پس همین تنها تعادل نش است.

ب) با استدلال مشابه قسمت الف، همه باید عدد ۱۰۰ را انتخاب کنند.

۲- برای همه‌ی حالت‌های جدول چک می‌کنیم! (۱۲ حالت ناقابل!)

ACF: نفر اول و دوم خوشحالند ولی نفر سوم ناراضی است. (تعادل نیست)

ACG: اول ناراضی پس تعادل نیست

ADF: اول ناراضی پس تعادل نیست

ADG: سوم ناراضی پس تعادل نیست

AEF: تعادل است!

AEG: اول ناراضی است.

BCF: اول ناراضی است.

BCG: تعادل است!

BDF: دوم ناراضی است.

BDG: دوم ناراضی است.

BEF: دوم ناراضی است.

BEG: اول ناراضی است.

پس دو تا حالت تعادل داریم: AEF و BCG.

۳- تعادل‌های نش یکی دقیقاً k نفر پول بدهند و یکی دیگر اینکه هیچ کس پول ندهد. C(n,k)+1 تا در کل.

۴- چون گفته سود هر کس به تعداد رأی‌هایی است که می‌آورد، پس در تعادل باید هر کس کل بازه‌اش را انتخاب کرده باشد. همه‌ی این حالت‌ها هم تعادل هستند چون کار بیشتری نمی‌توان کرد. هزینه هم ندارد. پس برای سمت چپ y=x و برای سمت راست هم y=x است.

۵- 

max_{p\in [0,1]} p^2+100p-2np^2

p = -50 +sqrt( 2500+2n-1)

0<= p <=1

1/2 <= n <= 51

ب) خیر. چون تعادلی که پیدا کردیم بهترین حالت است.

۶- الف) در حالتی که vi=bi باشد، در حالتی که سود برنده vi-bi باشد، چون vi-bi=0 پس با سود بقیه که ۰ است برابر است و تعادل نش است. در حالتی که سود برنده vi-max bj باشد، سود برنده vi-max vj است و بقیه ۰، پس چون برنده کسی است که بیشترین قیمت را داده است و سود آن مثبت است قیمت کمتر دادن سود برنده را بیشتر می‌کند و قیمت بیشتر دادن ضرر خود فرد را. پس این هم تعادل است.

ب) چون حالت تعادل حالت بهینه هم هست، چون از قیمت بقیه خبر نداریم، ممکن است برنده نشود. پس همه بیشترین قیمت یعنی vi را می‌دهند و ماکسیمم می‌برد.

ج) اگر هر فردی با این فکر که همه قیمت را کم داده‌اند قیمت کمتری بدهد اما کسی باشد که این کار را نکرده باشد و ببرد. چون حالت دیگر این است که چنین فردی نباشد و با سود زیادی ببرد.

مؤلفه‌های همبندی در گراف‌های بزرگ

http://www.mmds-data.org/presentations/vassilvitskii_mmds14.pdf

وقتی گراف بزرگ باشد، تمام آن در حافظه جا نمی‌شود. در نتیجه باید هر قسمت جداگانه انجام شود. به دلیل تبادل داده‌ی زیاد، الگوریتم‌های موازی هم خوب عمل نمی‌کنند. به همین دلیل روش‌هایی که برای حل مسایل به صورت محلی هستند و زمان کمی دارند اهمیت پیدا می‌کنند.