This seminar is offered for students enrolled in the Mathematics Master as module S4C1 as well as students enrolled in the Computer Science Master as module MA-INF 1205. The seminar is organized and held by Prof. Dr. Anne Driemel.

The goal of the seminar is for each participant to:

• Study a scientific paper (see references below)
• Present the main ideas of the paper in a talk (45 Minutes)
• Participate in discussions on the topic of the seminar
• Submit a written report (in own words) (10 pages)

The first preparation meeting will take place on Friday 31 January 2025, at 2:15 pm in room 2.050 (Informatik V, 2. OG) . The second preparation meeting will take place on Friday 11 April 2025, at 4:15 pm in the same room. The meeting room is located in the computer science building at Friedrich Hirzebruch Allee 8.

If you want to participate in the seminar and want to receive updates, please contact Prof. Dr. Anne Driemel with your topic preference from the literature list.

eCampus-Link for this course: https://ecampus.uni-bonn.de/goto_ecampus_crs_3673634.html

We will study approximation algorithms for variants of the discrete transportation problem. In the transportation problem we are given two point sets A and B in the plane, with a demand function that assigns each point in A and B a natual number. We are looking for a mapping from A to B, such that the demands are fulfilled and the overall transportation cost is minimized. Here, the transportation cost of one unit from point a to point b is usually defined by a distance function. A special case is the Earth Mover’s Distance, where the demands are 1 and the distance function is the Euclidean metric. In the seminar we will also study the problem of finding a rigid motion that minimizes EMD and conditional lower bounds for these problems.

- [AV04] Agarwal, Pankaj, und Kasturi Varadarajan. „A near-linear constant-factor approximation for euclidean bipartite matching?“ In Proceedings of the twentieth annual symposium on Computational geometry, 247–52. SCG 2004. https://doi.org/10.1145/997817.997856.

- [Indyk07] Indyk, Piotr. „A near linear time constant factor approximation for Euclidean bichromatic matching (cost)“. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 39–42. SODA 2007. http://ftp.eecs.umich.edu/~pettie/matching/Indyk-euclidean-matching-approximation.pdf

- [CGKR08] Cabello, Sergio, Panos Giannopoulos, Christian Knauer, und Günter Rote. „Matching point sets with respect to the Earth Mover’s Distance“. Computational Geometry 39, Nr. 2 (1. Februar 2008): 118–33. https://doi.org/10.1016/j.comgeo.2006.10.001.

- [SA12] Sharathkumar, R., und Pankaj K. Agarwal. „A near-linear time ε-approximation algorithm for geometric bipartite matching“. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 385–94. STOC 2012. https://doi.org/10.1145/2213977.2214014.

- [ANOY14] Andoni, Alexandr, Aleksandar Nikolov, Krzysztof Onak, und Grigory Yaroslavtsev. „Parallel Algorithms for Geometric Graph Problems“. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 574–83. STOC 2014. arXiv, 4. Januar 2014. https://doi.org/10.48550/arXiv.1401.0042.

- [Roha19] Rohatgi, Dhruv. „Conditional Hardness of Earth Mover Distance“. APPROX/RANDOM 2019 145 (2019): 12:1-12:17. https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.12.

- [AFPVX19] Agarwal, Pankaj K., Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, und Allen Xiao. „Faster Algorithms for the Geometric Transportation Problem“. 33rd International Symposium on Computational Geometry (SoCG 2017), https://doi.org/10.48550/arXiv.1903.08263.

- [Quan19] Quanrud, Kent. „Approximating Optimal Transport With Linear Programs“. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019), 6:1-6:9. https://doi.org/10.4230/OASIcs.SOSA.2019.6.

- [ACRX22] Agarwal, Pankaj K., Hsien-Chih Chang, Sharath Raghvendra, und Allen Xiao. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, „Deterministic, Near-Linear $\varepsilon$-Approximation Algorithm for Geometric Bipartite Matching“. https://doi.org/10.48550/arXiv.2204.03875.

- [ARSY24] Agarwal, Pankaj, Sharath Raghvendra, Pouyan Shirzadian, und Keegan Yao. „A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem“, Thirty-eighth Annual Conference on Neural Information Processing Systems, Neurips 2024. https://openreview.net/pdf?id=Xq0Jwbczkn

- [BSWW24] Bringmann, Karl, Frank Staals, Karol Węgrzycki, und Geert van Wordragen. „Fine-Grained Complexity of Earth Mover’s Distance under Translation“. https://doi.org/10.48550/arXiv.2403.04356.