بهترین زمان LP

طبق ویکیپدیا بهترین زمان O(n^3.5 L) است که L تعداد بیت‌های ورودی است.

http://en.wikipedia.org/wiki/Linear_programming#Projective_algorithm_of_Karmarkar

سوال این بود که تعداد بیت‌های ورودی چی است؟

این عکس را من از مقاله‌ی On the complexity of linear programming برداشتم که می‌گوید جمع بیت‌های لازم برای ماتریس A و بردار b است.

همچنان این سوال هست که روشهایی که در مورد Separating Oracle و اینها خواندیم به چه دردی می‌خورند؟ :)

جواب این است که الگوریتم ellipsoid کاری مثل جستجوی دودویی انجام می‌دهد و این Separating Oracle مثل چک کردن هر جواب است و کران بالا و پایین هم باید به دست بیاوریم. خود الگوریتم خیلی بهینه اینها را پیدا نمی‌کند و اگر ما از قبل بدانیم می‌توانیم بهتر از این حل کنیم.

http://www.cs.princeton.edu/courses/archive/fall05/cos521/ellipsoid.pdf

برای LP مسأله‌های Covering و Packing می‌شود PTAS در زمان خطی بر حسب تعداد قیدها پیدا کرد. (منبع همان صفحه‌ی ویکیپدیا)