Seminar: Selected Topics in Efficient Algorithms
General Information
- Lecturer: Prof. Dr. Susanne Albers
- Module: IN2107, IN8901, TUMonline
-
Time and Place:
The seminar will be held as a block seminar in July 2024.
Content
This seminar addresses Master's students in Computer Science with a scientific interest in the design and analysis of algorithms. The seminar participants will work on selected (research) literature. The papers cover a spectrum of topics, including (a) computational geometry, (b) graph algorithms, (c) algorithmic game theory, and (d) energy-efficient algorithms.
Seminar Topics
-
Computational Geometry: Convex Hulls
M. de Berg, O. Cheong, M. van Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition, Springer, 2008. Chapters 1 and 11, pp. 1-10 and 243-249.
- Computational Geometry: Line Segment Intersection
M. de Berg, O. Cheong, M. van Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition, Springer, 2008. Chapter 2, pp. 19-29.
- Computational Geometry: Point Location
M. de Berg, O. Cheong, M. van Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition, Springer, 2008. Chapter 6, pp. 121-137.
- Computational Geometry: Voronoi Diagrams
M. de Berg, O. Cheong, M. van Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition, Springer, 2008. Chapter 7, pp. 147-159.
- Online Matching in Bipartite Graphs
R.M. Karp, U.V. Vazirani and V.V. Vazirani. An optimal algorithm for online bipartite matching. Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC), 352-358, 1990.
B.E. Birnbaum and C. Kenyon. Online bipartite matching made simple. SIGACT News, 39(1):80-87, 2008.
N.R. Devanur, K. Jain and R.D. Kleinberg. Randomized primal-dual analysis of Ranking for online bipartite matching. Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 101-107, 2013.
- Online Matching with Augmentations
K. Chaudhuri, C. Daskalakis, R.D. Kleinberg and H. Lin. Online bipartite perfect matching with augmentations. Proc. 28th IEEE International Conference on Computer Communications (INFOCOM), 1044-1052, 2009.
- Opinion Formation in Social Networks
F. Chierichetti, J. Kleinberg and A. Panconesi. How to schedule cascades in an arbitrary graph. SIAM Journal on Computing, 43(6):1602-1623, 2008.
- Network Design: Fair Cost Allocation
E. Anshlevich, A. Dasgupta, J.M. Kleinberg, E. Tardos and T. Wexler. The price of stability in network design with fair cost allocation. SIAM Journal on Computing, 38(4):1906-1920, 2014.
- Network Design: Arbitrary Payments
E. Anshlevich, A. Dasgupta, E. Tardos and T. Wexler. Near optimal network design with selfish agents. Theory of Computing, 4(1):77-109, 2008.
- Network Creation Games
A. Fabrikant, A. Luthra, E.N. Maneva, C.H. Papadimitriou and S. Shenker. On a network creation game. Proc. 22nd ACM Symposium on Principles of Distributed Computing (PODC), 347-351, 2003.
N. Alon, E.D. Demaine, M.T. Hajiaghayi and T. Leighton Basic network creation games. SIAM Journal on Discrete Mathematics, 27(2):656-668, 2013.
- Power Management for a Single Device
S. Irani, S.K. Shukla and R. Gupta. Algorithms for power savings. ACM Trans. Algorithms, 3(4):41, 2007.
J. Augustine, S. Irani and C. Swamy. Optimal power-down strategies. SIAM J. Comput., 37(5):1499-1516, 2008.
- Dynamic Right-Sizing of Data Centers
S. Albers. On Energy Conservation in Data Centers. ACM Transactions on Parallel Computing. 6(3): 13:1-13:26, 2019.
- Approximation Algorithms: Basics
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. 3rd Edition. MIT Press 2009. ISBN 978-0-262-03384-8. Chapter 35.
-
Approximation Algorithms: Greedy and Local Search
D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms.. Cambridge University Press 2011. ISBN ISBN 978-0-521-19527-0. Chapter 2.