<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (josephzizys)</title>
    <link>https://pinboard.in/u:josephzizys/public/</link>
    <description>recent bookmarks from josephzizys</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="http://rjlipton.wordpress.com/2011/11/19/another-annoying-open-problem/"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="http://rjlipton.wordpress.com/2011/11/19/another-annoying-open-problem/">
    <title>Another Annoying Open Problem</title>
    <dc:date>2011-11-19T23:23:22+00:00</dc:date>
    <link>http://rjlipton.wordpress.com/2011/11/19/another-annoying-open-problem/</link>
    <dc:creator>josephzizys</dc:creator><description><![CDATA[
 The k-server problem: some progress, still wide open 





Aleksander Mądry gave a stellar talk at our ARC Theory Day a week ago Friday. He is an expert on algorithmic graph theory, among other areas of theory. Already he has multiple best-paper awards, including the paper of this talk from FOCS 2011, and I expect he will get more in the future. This is good going considering that basic LaTeX systems lack a macro for the Polish ogonek diacritic in his name—Ken installed a special package called tipa to get it while editing this post. 


Today I would like to talk about his result and the open questions that remain.




He with Nikhil Bansal, Niv Buchbinder, and Seffi Naor (BBMN) have made a recent important contribution to our understanding of the complexity of on-line algorithms. Aleksander’s talk was wonderful and explained what is known, their new result, and what still remains to be done. As he said:  


One of the remaining open questions is really annoying—it should be solved—but it continues to resist attacks.



Before I discuss their result I would like to thank the Theory Day organizers Prasad Tetali and Prasad Raghavendra. It was held on the magical day 11/11/11, which does not happen that often, and in fact Mądry’s talk spanned 11:11:11am. Ken wore a red shirt in Buffalo but could not find the WW I remembrance poppy pin he acquired during his sabbatical in Canada. The full scorecard of talks and titles was: 



Thomas Dueholm Hansen: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. 

Aleksander Mądry: Online algorithms and the k-server conjecture. 

Mohit Singh: A Randomized Rounding Approach for Symmetric TSP. 

Ryan Williams: Algorithms for Circuits and Circuits for Algorithms.


 The Problem 


The problem he spoke about is the now classic on-line server problem. The simplest case is the problem of managing a computer $. Note that this is the way to tell a theory talk on computer caches from an architecture talk on computer caches—in architecture often $ is used to denote a cache. Perhaps this is changing, given the current economic turmoil, perhaps not. 


The key is that there are  pages in the cache and  total pages. Each time a page is requested, if it is not in the cache the task is to decide which page to “evict” from the cache. If the strategy is deterministic, then as Danny Sleator and Bob Tarjan proved back in 1985, the best strategy is only -competitive. This means that the best deterministic strategy could be as bad as  times the best off-line strategy which is allowed to see all the page requests at once. 


Randomization comes to the rescue. If the strategy for eviction can be random, then it is known that an on-line random strategy exists that is  competitive. This is due to Amos Fiat, Dick Karp, Mike Luby, Lyle McGeoch, Danny Sleator, and Neal Young in 1991. 


The paging problem is just a special case of the general -server problem. In the general case the simple cache mechanism is replaced by one based on an arbitrary finite metric space. The servers at any step are located somewhere on the points of the metric space. The requests are to “serve” a point in the space: a server must move to that point, and it incurs a cost of the distance in the metric. 


In the 1990′s this problem was very “hot,” and there was a stream of results that tried to get good deterministic server strategies. The first results were exponential in  but independent of : recall there are  servers and the space has  points. Finally—in a famous paper—Elias Koutsoupias and Christos Papadimitriou 1994 showed that there is a strategy achieving , which remains today the best known result. 

 The BBMN Result 


The new result is: 


Theorem 1  There exists an -competitive on-line strategy for the -server problem. 



This is a great improvement, but it also changes the rules. It is great since the competitiveness bound is poly-log in . However, all the previous results we discussed had competitiveness bounds that did not depend on the size of the metric space, . Their result does. 


See their paper for the proof. The key idea is that they:  Reduce the -server problem over arbitrary metric to a (more difficult) problem over a very simple metric  The very simple metric is a type of tree-like metric. The proof relies on the fact that any metric space on  points can be well approximated by such a metric space. The cost of the approximation grows roughly as , so it is not surprising that their theorem has factors of  in the competitiveness bound.


 Open Problems 


The -server problem has the following bounds and gaps in those bounds: 



If the strategy is deterministic it must take  and can be done in . There is a small, but annoying gap of two here. Which is correct? 

 If the strategy is randomized it must take . There is a huge and annoying gap to the known upper bounds here. There is no known strategy for even the simple case of the real line that is randomized but beats linear in . What is going on?
 Finally, are the polylog factors of  in their result necessary? In particular can one get rid of the dependence on  altogether?


[fixed typo in Fiat et al. to O(log k)]

         



]]></description>
<dc:subject>1 All_Posts News Open_Problems Results Algorithms approximation deterministic lower_bounds randomness</dc:subject>
<dc:identifier>https://pinboard.in/u:josephzizys/b:e4775cd790d6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:1"/>
	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:All_Posts"/>
	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:News"/>
	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:Open_Problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:Results"/>
	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:Algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:deterministic"/>
	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:lower_bounds"/>
	<rdf:li rdf:resource="https://pinboard.in/u:josephzizys/t:randomness"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>