Dr Joachim Spoerhase

All publications

Journal articles

• Chalermsook P, Kaul M, Mnich M, Spoerhase J, Uniyal S & Vaz D (2024) Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter. ACM Transactions on Algorithms.
• Byrka J, Lewandowski M & Spoerhase J (2020) Approximating Node-Weighted k-MST on Planar Graphs. Theory of Computing Systems, 64(4), 626-644.
• Byrka J, Pensyl T, Rybicki B, Spoerhase J, Srinivasan A & Trinh K (2018) An Improved Approximation Algorithm for Knapsack Median Using Sparsification. Algorithmica, 80(4), 1093-1114.
• Fleszar K, Mnich M & Spoerhase J (2018) New algorithms for maximum disjoint paths based on tree-likeness. Mathematical Programming, 171(1-2), 433-461.
• Das A, Fleszar K, Kobourov S, Spoerhase J, Veeramoni S & Wolff A (2018) Approximating the Generalized Minimum Manhattan Network Problem. Algorithmica, 80(4), 1170-1190.
• Bekos MA, van Dijk TC, Fink M, Kindermann P, Kobourov S, Pupyrev S, Spoerhase J & Wolff A (2017) Improved Approximation Algorithms for Box Contact Representations. Algorithmica, 77(3), 902-920.
• Chimani M & Spoerhase J (2015) Approximating Spanning Trees with Few Branches. Theory of Computing Systems, 56(1), 181-196.
• Knauer M & Spoerhase J (2015) Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. Algorithmica, 71(4), 797-811.
• Das A, Gansner ER, Kaufmann M, Kobourov S, Spoerhase J & Wolff A (2015) Approximating Minimum Manhattan Networks in Higher Dimensions. Algorithmica, 71(1), 36-52.
• Kindermann P, Schulz A, Spoerhase J & Wolff A (2014) On Monotone Drawings of Trees, 488-500.
• Fink M, Haunert J-H, Spoerhase J & Wolff A (2013) Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation. IEEE Transactions on Visualization and Computer Graphics, 19(12), 2326-2335.
• Fink M, Haunert J-H, Schulz A, Spoerhase J & Wolff A (2012) Algorithms for Labeling Focus Regions. IEEE Transactions on Visualization and Computer Graphics, 18(12), 2583-2592.
• Spoerhase J & Wirth H-C (2010) Relaxed voting and competitive location under monotonous gain functions on trees. Discrete Applied Mathematics, 158(4), 361-373.
• Spoerhase J & Wirth H-C (2009) (r,p)-centroid problems on paths and trees. Theoretical Computer Science, 410(47-49), 5128-5137.
• Spoerhase J & Wirth H-C (2009) Optimally computing all solutions of Stackelberg with parametric prices and of general monotonous gain functions on a tree. Journal of Discrete Algorithms, 7(2), 256-266.
• Spoerhase J & Wirth H-C (2009) An algorithm for the single maximum coverage location or the -medianoid problem on trees. Information Processing Letters, 109(8), 391-394.
• Noltemeier H, Spoerhase J & Wirth H-C (2007) Multiple voting location and single voting location on trees. European Journal of Operational Research, 181(2), 654-667.

Chapters

• Chalermsook P, Gadekar A, Khodamoradi K & Spoerhase J (2023) Independent Set in k-Claw-Free Graphs: Conditional $$chi $$-Boundedness and the Power of LP/SDP Relaxations, Approximation and Online Algorithms (pp. 205-218). Springer Nature Switzerland
• Chimani M & Spoerhase J (2013) Approximating Spanning Trees with Few Branches, Approximation and Online Algorithms (pp. 30-41). Springer Berlin Heidelberg

Conference proceedings papers

• Spoerhase J, Abbasi F, Banerjee S, Byrka J, Chalermsook P, Gadekar A, Khodamoradi K, Marx D & Sharma R (2024) Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces. Proc. 51st International Colloquium on Automata, Languages and Programming (ICALP'24)
• Abbasi F, Banerjee S, Byrka J, Chalermsook P, Gadekar A, Khodamoradi K, Marx D, Sharma R & Spoerhase J (2023) Parameterized Approximation Schemes for Clustering with General Norm Objectives. Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS'23)
• Beck M, Spoerhase J & Storandt S (2023) Mind the Gap: Edge Facility Location Problems in Theory and Practice. Proc. 9th International Conference Algorithms and Discrete Applied Mathematics (CALDAM'23) (pp 321-334)
• Gutowski G, Mittelstädt F, Rutter I, Spoerhase J, Wolff A & Zink J (2023) Coloring Mixed and Directional Interval Graphs. Proc. 30th International Symposium Graph Drawing and Network Visualization (GD'22) (pp 418-431)
• Spoerhase J, Khodamoradi K, Riegel B, Ordozgoiti B & Gionis A (2023) A Constant-Factor Approximation Algorithm for Reconciliation k-Median. Proc. International Conference on Artificial Intelligence and Statistics (AISTATS'23)
• Firman O & Spoerhase J (2022) Hypergraph Representation via Axis-Aligned Point-Subspace Cover. Proc. 16th International Conference and Workshops Algorithms and Computation (WALCOM'22) (pp 328-339)
• Bosch Y, Schäfer P, Spoerhase J, Storandt S & Zink J (2021) Consistent Simplification of Polyline Tree Bundles. Proc. 27th International Computing and Combinatorics Conference (pp 231-243)
• Antoniadis A, Capretto M, Chalermsook P, Damerius C, Kling P, Nölke L, Obscura Acosta N & Spoerhase J (2021) On Minimum Generalized Manhattan Connections. Proc. 17th Algorithms and Data Structures Symposium (WADS'21) (pp 85-100)
• Byrka J, Lewandowski M, Meesum SM, Spoerhase J & Uniyal S (2020) PTAS for Steiner Tree on Map Graphs. Proc. 14th Latin American Symposium on Theoretical Informatics (LATIN'20) (pp 3-14)
• Beyer S, Chimani M & Spoerhase J (2020) A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs. Proc. 26th International Conference on Computing and Combinatorics (COCOON'20) (pp 347-359)
• Spoerhase J, Storandt S & Zink J (2020) Simplification of polyline bundles. Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'20), Vol. 162
• Mizrachi E, Schwartz R, Spoerhase J & Uniyal S (2019) A tight approximation for submodular maximization with mixed packing and covering constraints. Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP'19), Vol. 132
• Chan TM, Van Dijk TC, Fleszar K, Spoerhase J & Wolff A (2018) Stabbing rectangles by line segments - How decomposition reduces the shallow-cell complexity. Proc. 29th International Symposium on Algorithms and Computation (ISAAC'18), Vol. 123
• Byrka J, Lewandowski M & Spoerhase J (2018) Approximating Node-Weighted k-MST on Planar Graphs. Proc. 16th International Workshop on Approximation and Online Algorithms (WAOA'18) (pp 87-101)
• Chaplick S, De M, Ravsky A & Spoerhase J (2018) Approximation schemes for geometric coverage problems. Proc. 26th Annual European Symposium on Algorithms (ESA'18), Vol. 112
• Chaplick S, De M, Ravsky A & Spoerhase J (2018) Brief announcement: Approximation schemes for geometric coverage problems. Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP'18), Vol. 107
• Byrka J, Sornat K & Spoerhase J (2018) Constant-factor approximation for ordered k-median. Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC'18)
• Fleszar K, Mnich M & Spoerhase J (2016) New algorithms for maximum disjoint paths based on tree-likeness. Proc. 24th Annual European Symposium on Algorithms (ESA'16), Vol. 57
• Bereg S, Fleszar K, Kindermann P, Pupyrev S, Spoerhase J & Wolff A (2015) Colored Non-crossing Euclidean Steiner Forest. Proc. 26th International Symposium Algorithms and Computation (ISAAC'15) (pp 429-441)
• Byrka J, Pensyl T, Rybicki B, Spoerhase J, Srinivasan A & Trinh K (2015) An Improved Approximation Algorithm for Knapsack Median Using Sparsification. Proc. 23rd Annual European Symposium Algorithms (ESA'15) (pp 275-287)
• Lange S, Gebert S, Spoerhase J, Rygielski P, Zinner T, Kounev S & Tran-Gia P (2015) Specialized Heuristics for the Controller Placement Problem in Large Scale SDN Networks. Proc. 27th International Teletraffic Congress (ITC'15), 8 September 2015 - 10 September 2015.
• Chimani M & Spoerhase J (2015) Network design problems with bounded distances via shallow-light steiner trees. Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS'15), Vol. 30 (pp 238-248)
• Byrka J, Fleszar K, Rybicki B & Spoerhase J (2015) Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems. Proc. Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15)
• Gebert S, Hock D, Hartmann M, Spoerhase J, Zinner T & Phuoc Tran-Gia (2014) Including energy efficiency aspects in multi-layer optical network design. Proc. IEEE Fifth International Conference on Communications and Electronics (ICCE'14), 30 July 2014 - 1 August 2014.
• Bekos MA, van Dijk TC, Fink M, Kindermann P, Kobourov S, Pupyrev S, Spoerhase J & Wolff A (2014) Improved Approximation Algorithms for Box Contact Representations. Proc. 22th Annual European Symposium on Algorithms (ESA'14) (pp 87-99)
• Das A, Fleszar K, Kobourov S, Spoerhase J, Veeramoni S & Wolff A (2013) Approximating the Generalized Minimum Manhattan Network Problem. Proc. 24th International Symposium on Algorithms and Computation (ISAAC'13) (pp 722-732)
• van Dijk TC, Fleszar K, Haunert J-H & Spoerhase J (2013) Road segment selection with strokes and stability. Proceedings of the 1st ACM SIGSPATIAL International Workshop on MapInteraction
• Fink M, Haunert J-H, Mchedlidze T, Spoerhase J & Wolff A (2012) Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. Proc. 6th International Workshop Algorithms and Computation (WALCOM'12) (pp 186-197)
• Schwartges N, Spoerhase J & Wolff A (2011) Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs. Proc. 9th International Workshop Approximation and Online Algorithms (WAOA'11) (pp 77-88)
• Das A, Gansner ER, Kaufmann M, Kobourov S, Spoerhase J & Wolff A (2011) Approximating Minimum Manhattan Networks in Higher Dimensions. Proc. 19th Annual European Symposium Algorithms (ESA'11) (pp 49-60)
• Fink M & Spoerhase J (2011) Maximum Betweenness Centrality: Approximability and Tractable Cases. Proc. 5th International Workshop Algorithms and Computation (WALCOM'11) (pp 9-20)
• Spoerhase J (2010) An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems. Proc. 21st International Symposium on Algorithms and Computation (ISAAC'10) (pp 440-450)
• Knauer M & Spoerhase J (2009) Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. Proc. 11th Algorithms and Data Structures Symposium (WADS'09) (pp 459-470)
• Spoerhase J & Wirth HC (2008) Approximating (r, p)-Centroid on a path. Proc. 7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW'08) (pp 193-195)

Preprints

• Abbasi F, Banerjee S, Byrka J, Chalermsook P, Gadekar A, Khodamoradi K, Marx D, Sharma R & Spoerhase J (2023) Parameterized Approximation Schemes for Clustering with General Norm Objectives.
• Byrka J, Sornat K & Spoerhase J (2017) Constant-Factor Approximation for Ordered k-Median.
• Chaplick S, De M, Ravsky A & Spoerhase J (2016) Approximation Schemes for Geometric Coverage Problems.
• Fleszar K, Mnich M & Spoerhase J (2016) New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness.
• Chimani M & Spoerhase J (2014) Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees.
• Fink M, Haunert J-H, Mchedlidze T, Spoerhase J & Wolff A (2011) Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles.
• Das A, Gansner ER, Kaufmann M, Kobourov S, Spoerhase J & Wolff A (2011) Approximating Minimum Manhattan Networks in Higher Dimensions.
• Spoerhase J (2010) An Optimal Algorithm for the Indirect Covering Subtree Problem.
• Spoerhase J, Abbasi F, Banerjee S, Byrka J, Chalermsook P, Gadekar A, Khodamoradi K, Dániel M & Sharma R () Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces, https://arxiv.org/abs/2305.07316.