Date: | Tue, 12 Dec 2017 18:33:23 +0000 |
---|---|
From: | Shuchi Chawla <shuchi@xxxxxxxxxxx> |
Subject: | Re: [theory students] [theory faculty] Theory lunch and TCS+ talk noon tomorrow: k-server via multiscale entropic regularization |
To follow up on Ben's message, this year seems to have been the year of big algorithmic breakthroughs. A few weeks back we heard about the new constant factor approximation for ATSP. Tomorrow's talk will likewise talk about the (almost) resolution of a major conjecture. The k-server conjecture states that there exists an O(log k) competitive online algorithm for the k-server problem. This has been the most important open problem in online algorithms for 25 years. James Lee recently announced a polylog(k) competitive algorithm for general metrics. SeeÂhttps://homes.cs.washington.edu/~jrl/papers/fusion.pdf. Competitive ratios of all previously known algorithms had either a polynomial dependence on k, or a dependence on the size of the instance, n. The topic of tomorrow's talk is a key step in James' eventual proof. Shuchi On Tue, Dec 12, 2017 at 11:59 AM Benjamin Miller <bmiller@xxxxxxxxxxx> wrote:
|
[← Prev in Thread] | Current Thread | [Next in Thread→] |
---|---|---|
|
Previous by Date: | [theory students] Theory lunch and TCS+ talk noon tomorrow: k-server via multiscale entropic regularization, Benjamin Miller |
---|---|
Next by Date: | Re: [theory students] [theory faculty] Theory lunch and TCS+ talk noon TODAY: k-server via multiscale entropic regularization, Benjamin Miller |
Previous by Thread: | [theory students] Theory lunch and TCS+ talk noon tomorrow: k-server via multiscale entropic regularization, Benjamin Miller |
Next by Thread: | Re: [theory students] Theory Lunch and TCS+ TODAY at noon, Benjamin Miller |
Indexes: | [Date] [Thread] |