Lasse Kliemann

I am a member of the research group of Prof. Dr. A. Srivastav in Kiel. My work is partly supported by the DFG Priority Program Algorithm Engineering.

Research Interests

• Algorithm engineering;
• Streaming algorithms;
• Distributed network formation (network creation games);
• Approximation algorithms for hypergraph covering and packing.

Peer-Reviewed Publications

For most of the following publications, I am allowed to provide a self-archived version. I have not uploaded all of those PDF files yet. Please contact me if you need any of the missing files.

• Bipartite Matching in the Semi-Streaming Model. With Sebastian Eggert, Peter Munstermann, and Anand Srivastav. Algorithmica, August 2011. Document ID: 519a88bb-5f5a-409d-8293-13cd80a66b36. Download original publication at Springer (may require payment) or self-archived version for screen viewing (free) or self-archived version for printing (free).
• The Price of Anarchy for Network Formation in an Adversary Model. Games 2 number 3, pages 302–332, 2011. Download original publication at MDPI (free).
• Matching in Bipartite Graph Streams in a Small Number of Passes (Extended Abstract). In: Proceedings of the 10th International Symposium on Experimental Algorithms, Kolimpari, Chania, Creete, May 2011 (SEA 2011), pages 254 – 266, published in 2011. Document ID: dda51148-ac5b-4655-9c4f-e01f26511235. Download original publication at Springer (may require payment) or self-archived version for screen viewing (free) or self-archived version for printing (free). Download the presentation that I gave at SEA 2011.
• Brief Announcement: The Price of Anarchy for Distributed Network Formation in an Adversary Model. In: Proceedings of the 29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Zurich, Switzerland, July 2010 (PODC 2010), pages 229 – 230, published in 2010. Download original publication at ACM (may require payment).
• Bipartite Graph Matchings in the Semi-Streaming Model (Extended Abstract). With Sebastian Eggert and Anand Srivastav. In: Proceedings of the 17th Annual European Symposium on Algorithms, Copenhagen, Denmark, September 2009 (ESA 2009), pages 492 – 503, published in 2009. Download original publication at Springer (may require payment) or self-archived version (free). This work has also been presented at the MADALGO Workshop on Massive Data Algorithmics, June 2009, Århus, Denmark.
• Experimental Study of Non-oblivious Greedy and Randomized Rounding Algorithms for Hypergraph b-Matching (Extended Abstract). With Anand Srivastav. In: Proceedings of the 8th International Symposium on Experimental Algorithms, Dortmund, Germany, June 2009 (SEA 2009), pages 185 – 196, published in 2009. Download original publication at Springer (may require payment).
• Models of Non-atomic Congestion Games – From Unicast to Multicast Routing. With Anand Srivastav. In: Jürgen Lerner, Dorothea Wagner and Katharina A. Zweig (eds.), Algorithmics of Large and Complex Networks, pages 292 – 318, published in 2009. Download original publication at Springer (may require payment).
• Parallel Algorithms via the Probabilistic Method. With Anand Srivastav. In: Sanguthevar Rajasekaran and John H. Reif (eds.), Parallel Computing: Models, Algorithms, and Applications, Chapman & Hall/CRC, 61 pages, published in 2008. Download preliminary version (free).
• Randomized Algorithms for Mixed Matching and Covering in Hypergraphs in 3D Seed Reconstruction in Brachytherapy. With Helena Fohlin and Anand Srivastav. In: Carlos J. S. Alves, Panos M. Pardalos, Luis N. Vicente (eds.), Optimization in Medicine, Springer, pages 71 – 102, published in 2008. Download preliminary version as technical report 0611 (free). This work was also presented at the Workshop on Optimization in Medicine, Coimbra, Portugal, 2005.
• Three-dimensional reconstruction of seed implants by randomized rounding and visual evaluation With Frank-André Siebert, Anand Srivastav, Helena Fohlin, and György Kovács. Medical Physics 34(3), pages 967–975, published in 2007. Download original publication at Medical Physics (may require payment).
• The Price of Anarchy in Selfish Multicast Routing. With Andreas Baltz, Sandro Esquivel, and Anand Srivastav. In: Revised Papers of the 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking, Chester, UK, June 2006 (CAAN 2006), pages 5 – 18, published in 2006. Download original publication at Springer (may require payment).
• Spectral Analysis. With Andreas Baltz. In: Ulrik Brandes, Thomas Erlebach (eds.), Network Analysis, pages 373-416, published in 2005. Download original publication at Springer (may require payment).

Non Peer-Reviewed Publications

• The Price of Anarchy and Computation of Equilibria in Non-atomic Consumption-Relevance Congestion Games. Technical Report 0814, 36 pages, published in 2008. Download from university archive (free) or local copy (free).
• Experimental Studies of the Price of Anarchy in Non-atomic Consumption-Relevance Congestion Games. Technical Report 0815, 39 pages, published in 2008. Download from university archive (free) or local copy (free).

Dissertation

Teaching

Courses

For courses see our main teaching site, mostly in German.

Additional Material (Partly in German)

• A Note on "Reordering" Infinite Sums (Revision 5753)
• Aufgaben und Lösungen zu DSW 2010 (SVN Revision 5767)

Short CV

• Born 1975 in Germany.
• 1996 began study of physics and later also mathematics at CAU Kiel.
• Since 2003 engaged in Prof. Srivastav's research group.
• PhD (Dr. rer. nat.) January 2010, Dissertation published November 2010.

Technical Documents

• The Subversion revision control system: slides in PDF and LaTeX source.
• HOWTOs for frequently occuring technical problems and tasks. (In part only relevant for members of our research group.)
• My presentations (slides in English) from the Vorkurs Informatik 2010.