Exchange argument in Greedy Algorithms

Recently I started reading this algorithm textbook for my CS330 class next semester – Algorithm Design by Jon Kleinberg and Eva Tardos. Today I am going to record my thoughts on Chapter 4.3 – Exchange argument.

Exchange argument is actually the name of a method used to prove a type of greedy algorithm. The question that we focus on is as follows: Suppose there is a computer with limited cache memory, and we need to process a sequence of data from the main memory. What is the best order to “evict” certain data and retrieve data from the main memory so that the total number of times we evict (misses) is the least?

According to Les Belady, the best way to do this is to evict the “farthest-in-the-future” item in the cache memory. For example, consider a sequence like a b c d a d e a d b c and a cache memory of size 3 with initially a b c in it. The best plan is to evict c at step 4 becuase it is “farthest-in-the-future”.

The proof uses the method of “exchange argument”, in which we first suppose the best way to do this, say S, and our plan, say S*, and we revise our plan so that it eventually is identical to S, in the meantime follows our “farthest-in-the-future” rule.

Assume the first j steps of S and S* are identical, so now we have the same sequence of data in cache memories. For the (j + 1)st step, say S evicts the item e but S* evicts f since f is farthest. We would like S* to “come back” to S as soon as possible and avoid adding any more misses. Now consider the (j + 2)nd request.

If there is a request to item g which is not equal to either e or f:

If S evicts any item other than f, we would simply let S* also evict that item. After this step two cache memories would be identical, job done. Else, S evicts f, we would let S* evict e. In this way two cache memories are again identical. Hooray.

Else, there is a request to e:

Note that S*’s cache memory now contains e. If S evicts f, two cache memories are now equal. If S evicts some f’ other than f instead, we would also let S* evict f’, and bring f, then again voila.

There can’t be a request to f before to e because we already know f is farther than e.

The proof above is not complete, but the spirit is shown: first assume we have the best solution, and try to prove that our solution is the best by closing the gap. Quite amazing.

13 thoughts on “Exchange argument in Greedy Algorithms”

  1. 倩碧卓越润肤乳,全新的倩碧有油黄油.升级配方,创新修护科技,提升弹润膜力,带来内润外弹光采肌.全新倩碧天才黄油+,专注修护天然肌肤保护膜力,成就弹润膜力升级,内润外弹,卓效不凡,倩碧小黄油带来更好的滋润护肤体验!

  2. 從柯P現象看投資 財經專家謝金河:選後台股 局勢很好! @ 察爾斯大夫 美麗殿堂 Dr. Charles Meridien Palace :: 痞客邦 :: 從柯P現象看投資財經專家謝金河:選後台股 局勢很好! 日期:2014-12-03 作者:口述/謝金河 整理/段詩潔 出處:財訊第 465 期 有人問我選後怎麼看台股行情?我說:「局勢很好!」 首

  3. Hi there would you mind sharing which blog platform you’re using? I’m planning to start my own blog in the near future but I’m having a difficult time choosing between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your design and style seems different then most blogs and I’m looking for something unique. P.S Apologies for getting off-topic but I had to ask!

  4. JUVEDERM由透明質酸Hyaluronic Acid(一種天然多醣體)製造而成,並具有幼滑及高凝聚力的配方。透明質酸(HA)是皮膚組織的主要成份之一,能自然存在於人體肌膚內 JUVEDERM所用的透明質酸非由動物身體提取,可鎖住水份保濕皮膚,從而增加皮膚密度並改善質感 Juvederm 玻尿酸 加強優化面部輪廓,可被身體完全吸引,能自然地修飾面部輪廓 功效可長達24個月以上 JUVEDERM的特點: 效果立即可見 非永久性 非手術性 安全有效 效果自然 JUVEDERM獲歐盟(CE)及美國及藥物管理局(FDA)認證 首先及唯一獲得FDA認證在首次療程後能維持長達一年2-4功效 新世代專員Hylacross科技為產品帶來獨特的物理特質,包括凝聚力、支撐力及柔順度 這是一套由全球著名醫學美容醫生Dr. Maurício de Maio,以JUVÉDERM®系列透明質酸產品為基礎而研發的面部優化療程,藉著簡單程序便達致面部優化效果,不需進行手術,減低風險。

  5. Derma Veil ® 被喻為新世代逆齡完美輪廓塑造,最新一代的PLLA膠原。 2003年獲得Mexican Ministry of Health (SSA)認證及美國FDA出口認證,並於2006年在拉丁美洲及遠東至東南亞地區廣泛使用,多個臨床實例見證能改善老化、遺傳、疾病(如脂肪萎縮)等引起的凹陷問題,其效果備受認同。蘊含兩大活性成分均具有生物兼容性及分解性,可逐步被人體自然分解吸收,有效塑造童顏肌 : 1. 聚左乳酸 (Poly-L-lactic acid / PLLA) : 促進骨膠原生長 2. 甘醇酸(Glycolic Acid ) 使皮膚表皮層黏膠性脂質鬆軟,改善皮膚厚度,加速細胞再生,減少皺紋及疤痕,加強保濕功能,增加光澤,美白效果。 由於甘醇酸分子較小,容易滲透皮膚 治療前: 皮膚的凹陷/皺紋 治療後: 成分被人體吸收、並刺激膠原增生,撫平皺紋及凹陷部位。 注入BOTOX(保妥適)會抑制突觸前膜釋放神經遞質,阻斷乙酰膽鹼(Acetylcholine)的釋放,從而使肌肉張力下降或癱瘓麻痺,皺紋也隨之而逐漸消失。

  6. Yeezy http://www.yeezy.com.co/
    Yeezys http://www.yeezys.us.com/
    Yeezy http://www.yeezysupply.us.com/
    Yeezy Boost 350 http://www.yeezy-shoes.us.com/
    Yeezy Boost http://www.yeezy-boost350.com/
    Yeezy Boost 350 V2 http://www.yeezyboost350.us.com/
    Yeezy Boost 350 V2 Blue Tint http://www.yeezybluetint.com/
    Yeezy 500 Utility Black http://www.yeezy500utilityblack.com/
    Adidas Yeezy 500 http://www.yeezy500utilityblack.us/
    Vapor Max http://www.vapor-max.org.uk/
    Salomon http://www.salomon-shoes.org.uk/
    Salomon Shoes http://www.salomons.me.uk/
    Salomon Speedcross 4 http://www.salomonspeedcross4.org.uk/
    Off White Jordan http://www.offwhitejordan1.com/
    Nike Air VaporMax http://www.nikevapormax.org.uk/
    Nike Element 87 http://www.nikereactelement87.us.com/
    React Element 87 http://www.nikereactelement87.us/
    Nike Air Vapormax Plus http://www.nikeplus.us/
    Nike Outlet Store http://www.nike–outlet.us/
    Nike Outlet Store Online Shopping http://www.nikeoutletstoreonlineshopping.us/
    Nike Outlet Store http://www.nikeoutletonlineshopping.us/
    Cheap Nike NBA Jerseys http://www.nikenbajerseys.us/
    Air Max Nike http://www.nikeairmax.us/
    Nike Air Max 2017 http://www.max2017.us/
    Jordan Shoes http://www.jordan-com.com/
    Jordan 11 Concord http://www.jordan11-concord.com/
    Cheap Yeezy Shoes http://www.cs7boots1.com/
    Cheap NBA Jerseys From China http://www.cheapnba-jerseys.us/
    Birkenstock Sandals UK http://www.birkenstocksandalsuk.me.uk/
    Basketball Jersey http://www.basketball-jersey.us/
    Balenciaga http://www.balenciaga.me.uk/
    Balenciaga http://www.balenciagauk.org.uk/
    Balenciaga http://www.balenciagatriples.org.uk/
    Balenciaga http://www.birkenstocks.me.uk/
    Balenciaga UK http://www.balenciagatrainers.org.uk/
    Nike Air Max http://www.airmax270.org.uk/
    Yeezy Shoes http://www.adidasyeezyshoes.org.uk/
    Adidas Yeezy Shoes http://www.adidasyeezyshoes.org.uk/

Leave a Reply