前沿算法

2024-10-13, last class, same room. 10:20-11:55.

Final project:

Due on 10/31. Please send it to [email protected]. Together with your ID and name.

Either select any one of the papers below and summarize it. Or, pick any STOC/FOCS/SODA paper and summarize it.

It should be a 1 page summary. More pages are okey.

• Cole, Richard (1987), “Slowing down sorting networks to obtain faster sorting algorithms”, Journal of the ACM, 34 (1): 200–208, doi:10.1145/7531.7537
• Chan, Timothy, “Improved Deterministic Algorithms for Linear Programming in Low Dimensions”, ACM Transactions on Algorithms (TALG), Volume 14, Issue 3
• E. Zemel, An O(n) algorithm for the linear multiple choice knapsack problem and related problems, 18 (1984) 123–128 10.1016/0020-0190(84)90014-0.
• R. Jacob, Binary search on two-dimensional data, Technische Universität München, 2008.
• H. Kaplan, L. Kozma, O. Zamir, U. Zwick, Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps, in: J.T. Fineman, M. Mitzenmacher (Eds.), 2nd Symposium on Simplicity in Algorithms (SOSA 2019), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018: pp. 5:1–5:21 10.4230/OASIcs.SOSA.2019.5.
• N. Chiba, T. Nishizeki, Arboricity and Subgraph Listing Algorithms, SIAM Journal on Computing. 14 (1985) 210–223 10.1137/0214017.
• R. Reitzig, S. Wild, Building fences straight and high: An optimal algorithm for finding the maximum length you can cut k times from given sticks, Algorithmica. (2017) 10.1007/s00453-017-0392-3.