ترجمه فارسی مقاله الگوریتم حل نامکرر برای برنامه‌ریزی خطی آنلاین

چکیده

Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications, such as online auction, network revenue management and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former one typically guarantees better performance, even offering a constant regret, but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithm only requires first-order computations but induces a worse performance, lacking a constant regret bound. In this work, we bridge the gap between these two extremes by proposing an algorithm that achieves a constant regret while solving LPs only $O(loglog T)$ times over the time horizon $T$. Moreover, when we are allowed to solve LPs only $M$ times, we propose an algorithm that can guarantee an $Oleft(T^{(1/2+ε)^{M-1}}right)$ regret. Furthermore, when the arrival probabilities are known at the beginning, our algorithm can guarantee a constant regret by solving LPs $O(loglog T)$ times, and an $Oleft(T^{(1/2+ε)^{M}}right)$ regret by solving LPs only $M$ times. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.

چکیده به فارسی (ترجمه ماشینی)

برنامه نویسی خطی آنلاین (OLP) به دلیل کاربردهای گسترده خود مانند حراج آنلاین ، مدیریت درآمد شبکه و تبلیغات ، مورد توجه محققان و پزشکان قرار گرفته است.الگوریتم های OLP موجود در دو دسته قرار می گیرند: الگوریتم های مبتنی بر LP و الگوریتم های بدون LP.سابق به طور معمول عملکرد بهتری را تضمین می کند ، حتی یک پشیمانی مداوم نیز ارائه می دهد ، اما نیاز به حل تعداد زیادی از LP ها دارد که می تواند از نظر محاسباتی گران باشد.در مقابل ، الگوریتم بدون LP فقط به محاسبات مرتبه اول نیاز دارد اما عملکرد بدتری را القا می کند و فاقد پشیمانی مداوم است.در این کار ، ما با پیشنهاد الگوریتمی که در حین حل LP ها فقط $ O ( log log t) $ بار در طول افق زمانی $ t $ ، شکاف بین این دو افراط را ایجاد می کنیم.علاوه بر این ، هنگامی که ما مجاز به حل LPS فقط $ m $ $ هستیم ، ما یک الگوریتم را پیشنهاد می کنیم که می تواند یک $ o سمت چپ (t^{(1/2+ε)^{m-1}}} راست) را تضمین کند.بشرعلاوه بر این ، هنگامی که احتمالات ورود در ابتدا شناخته شده است ، الگوریتم ما می تواند با حل LPS $ O ( log log t) $ ، و یک $ O سمت چپ ، پشیمانی مداوم را تضمین کند (T^{(1/2+ε)^{M}} RIGHT) $ با حل LPS فقط $ m $ پشیمان می شود.آزمایش های عددی برای نشان دادن کارآیی الگوریتم های پیشنهادی انجام می شود.