近似算法讨论班 (Fall 2011) and W.D. Hamilton: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
imported>Etone
 
imported>Macdonald-ross
(prose...)
 
Line 1: Line 1:
= Syllabus =
'''William Donald Hamilton''' [[Royal Society|FRS]] (1 August 1936 – 7 March 2000) was an [[English people|English]] [[evolutionary biology|evolutionary biologist]] whom [[Richard Dawkins]] praised as one of the greatest [[evolution]]ary theorists of the 20th century.<ref>[http://www.edge.org/3rd_culture/hamilton/hamilton_index.html Obituary by Richard Dawkins – ''The Independent'' – 10 March 2000]</ref>
*'''Time''': every Thursday, 6:30pm.
* '''Place''': CS building, 228.


* '''Organizer''': 尹一通
Hamilton became famous through his [[Theory|theoretical]] work on [[kin selection]] and [[altruism]]. He explained its [[Genetics|genetic]] basis, and this was a key part of the  gene-centered view of [[evolution]]. In doing this, he became one of the forerunners of [[sociobiology]], as popularized by [[E.O. Wilson]]. Hamilton was certainly a big influence on Dawkins. He also published important work on [[sex ratio]]s and the [[evolution of sex]]. From 1984 to his death in 2000, he was the [[Royal Society]] Research Professor at [[Oxford University]]. He died of [[malaria]] contracted in the [[Democratic Republic of the Congo]].
:* office: CS building, 804
:* email: yitong.yin@gmail.com


=== Reference materials ===
== Hamilton's equation ==
* Vijay Vazirani. ''Approximation Algorithms''. Springer, 2004.
Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.<ref>Hamilton W.D. 1996. ''Narrow roads of geneland: the collected papers of W.D. Hamilton'', vol 1. Freeman, Oxford.</ref> The gene will spread if '''r'''x'''b''' is greater than '''c''':
* David Williamson and David Shmoys. ''The Design of Approximation Algorithms''. Cambridge Univ Press, 2011.
:<math>rb > c \ </math>   
* Michel Goemans. [http://www-math.mit.edu/~goemans/notes-lp.ps ''Linear Programming'']. Lecture notes of ''Advanced Algorithms'' class at MIT.
where:
* Venkatesan Guruswami and Ryan O'Donnell. [http://www.cs.washington.edu/education/courses/cse533/05au/ ''The PCP Theorem and Hardness of Approximation''].
* <math>c \ </math> is the reproductive cost to the altruist,
* <math>b \ </math> is the reproductive benefit to the recipient of the altruistic behavior, and
* <math>r \ </math> is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".


= Schedule =
== Collected papers ==
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors.
|-
 
|bgcolor="#A7C1F2" align="center"|'''Dates'''
* Hamilton W.D. 1996. ''Narrow roads of gene land vol. 1: Evolution of social behaviour''. Freeman, Oxford. ISBN 0-7167-4530-5
|bgcolor="#A7C1F2" align="center"|'''Speakers'''
* Hamilton W.D. 2002. ''Narrow roads of gene land vol. 2: Evolution of sex''. Oxford University Press, Oxford. ISBN 0-19-850336-9
|bgcolor="#A7C1F2" align="center"|'''Topics'''
* Hamilton W.D. 2005. ''Narrow roads of gene land, vol. 3: Last words'' (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5
|bgcolor="#A7C1F2" align="center"|'''Readings'''
 
|-
== References ==
|9.26
{{Reflist}}
|align="center"|张驰豪<br>(上海交通大学)|| Introduction to approximation algorithms.<br> Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms.||Chap. 1 of<br>Williamson-Shmoys.
 
|-
{{DEFAULTSORT:Hamilton, William Donald}}
|10.8
[[Category:1936 births]]
|align="center"|张驰豪<br>(上海交通大学)|| Greedy algorithms and local search.<br> Scheduling with deadlines; <math>k</math>-center; minimize makespan; metric TSP; min-degree spanning tree. || Chap. 2.1-2.4 of<br>Williamson-Shmoys.
[[Category:2000 deaths]]
|-
[[Category:English mathematicians]]
|10.13
[[Category:Geneticists]]
|align="center"|詹宇森<br>蒋炎岩<br>尹一通|| Local search (cont.). Scale and round.<br> Min-degree spanning tree; local search; potential analysis; <br>Knapsack; dynamic programming; pseudo-polynomial time; scale and round; FPTAS.||Chap. 2.6, 3.1 of<br>Williamson-Shmoys.
[[Category:English evolutionary biologists]]
|-
[[Category:Fellows of the Royal Society]]
|10.20
!colspan="3"|<font color=red>老师出差,暂停一次。</font>
|-
|10.27
|align="center"| 陈嘉||  Linear Programming.<br> Linear Programming; the simplex method; duality; strong duality theorem; von Neumann's minmax theorem.
|| [[media:Lp_no_pause.pdf‎|<nowiki>[</nowiki>slides<nowiki>]</nowiki>]]<br>[http://www-math.mit.edu/~goemans/notes-lp.ps Geomans' notes on LP]
|-
|11.4
|align="center"| 周源 <br>(Carnegie Mellon University)|| Approximation (and inapproximability) of MAX-CUT.<br> MAX-CUT; the probabilistic method; semi-definite programming (SDP); rounding SDP;<br> inapproximability; gap-reduction; probabilistically checkable proofs (PCP); the PCP theorem; <br> label cover game; parallel repetition theorem; unique label cover game; the unique games conjecture (UGC); <br> Boolean function; Fourier transformation; Parseval's identity; influence; noise operator; stability;<br>long code reduction; majority is the stablest (MIS);
||Chap. 6.1, 6.2 of<br>Williamson-Shmoys.<br>[http://www.cs.washington.edu/education/courses/cse533/05au/ PCP lecture at UW]<br> by Guruswami and O'Donnell
|-
|11.10
|align="center"|张驰豪<br>(上海交通大学)<br>尹一通|| Scale and round (cont.). Deterministic rounding of LP. <br> Bin packing; first-fit; exhaustive search; polynomial-time approximation scheme (PTAS). <br>Scheduling on a single machine; completion time; preemptive; shortest remaining processing time (SRPT); <br>the ellipsoid algorithm; separation oracle. || Chap. 3.3, 4.1-4.3 of<br> Williamson-Shmoys.
|-
|11.17
|align="center"|张驰豪<br>(上海交通大学)|| The primal-dual method. || Chap. 7.1-7.4 of<br> Williamson-Shmoys.
|-
|11.24
|align="center"|朱小虎<br>张驰豪<br>(上海交通大学)|| The Steiner tree problem. ||
|-
|12.1
|align="center"|詹宇森<br>张驰豪<br>(上海交通大学)|| Prize-collection Steiner tree; rounding; derandomization. ||
|-
|12.8
|align="center"|陈嘉|| Algorithmic Game Theory.<br>Strategic games; mechanism design; combinatorial auction; Vickrey auction; VCG auction. ||
|-
|12.15
|align="center"|尹一通|| Approximate counting; correlation decay; spin systems. ||
|}

Latest revision as of 09:43, 22 December 2013

William Donald Hamilton FRS (1 August 1936 – 7 March 2000) was an English evolutionary biologist whom Richard Dawkins praised as one of the greatest evolutionary theorists of the 20th century.[1]

Hamilton became famous through his theoretical work on kin selection and altruism. He explained its genetic basis, and this was a key part of the gene-centered view of evolution. In doing this, he became one of the forerunners of sociobiology, as popularized by E.O. Wilson. Hamilton was certainly a big influence on Dawkins. He also published important work on sex ratios and the evolution of sex. From 1984 to his death in 2000, he was the Royal Society Research Professor at Oxford University. He died of malaria contracted in the Democratic Republic of the Congo.

Hamilton's equation

Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.[2] The gene will spread if rxb is greater than c:

[math]\displaystyle{ rb \gt c \ }[/math]

where:

  • [math]\displaystyle{ c \ }[/math] is the reproductive cost to the altruist,
  • [math]\displaystyle{ b \ }[/math] is the reproductive benefit to the recipient of the altruistic behavior, and
  • [math]\displaystyle{ r \ }[/math] is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".

Collected papers

Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors.

  • Hamilton W.D. 1996. Narrow roads of gene land vol. 1: Evolution of social behaviour. Freeman, Oxford. ISBN 0-7167-4530-5
  • Hamilton W.D. 2002. Narrow roads of gene land vol. 2: Evolution of sex. Oxford University Press, Oxford. ISBN 0-19-850336-9
  • Hamilton W.D. 2005. Narrow roads of gene land, vol. 3: Last words (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5

References

Template:Reflist

  1. Obituary by Richard Dawkins – The Independent – 10 March 2000
  2. Hamilton W.D. 1996. Narrow roads of geneland: the collected papers of W.D. Hamilton, vol 1. Freeman, Oxford.