Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

Publications (chronologically)

Publications

2025[ to top ]
  • Clustering to Minimize Cluster-Aware Norm Objectives. Herold, Martin G.; Kipouridis, Evangelos; Spoerhase, Joachim. In Proc. 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’25). 2025.
  • Approximating Traveling Salesman Problems Using a Bridge Lemma. Böhm, Martin; Friggstad, Zachary; Mömke, Tobias; Spoerhase, Joachim. In Proc. 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’25). 2025.
2024[ to top ]
  • Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces. Abbasi, Fateme; Banerjee, Sandip; Byrka, Jaroslaw; Chalermsook, Parinya; Gadekar, Ameet; Khodamoradi, Kamyar; Marx, Dániel; Sharma, Roohani; Spoerhase, Joachim. In Proc. 51st International Colloquium on Automata, Languages and Programming (ICALP’24). 2024.
  • Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter. Chalermsook, Parinya; Kaul, Matthias; Mnich, Matthias; Spoerhase, Joachim; Uniyal, Sumedha; Vaz, Daniel. In ACM Transactions on Algorithms. 2024.
2023[ to top ]
  • A Constant-Factor Approximation Algorithm for Reconciliation $k$-Median. Spoerhase, Joachim; Khodamoradi, Kamyar; Riegel, Benedikt; Ordozgoiti, Bruno; Gionis, Aristides. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS’23), Vol. 206, pp. 1719–1746. {PMLR}, 2023.
  • Parameterized Approximation Schemes for Clustering with General Norm Objectives. Abbasi, Fateme; Banerjee, Sandip; Byrka, Jaroslaw; Chalermsook, Parinya; Gadekar, Ameet; Khodamoradi, Kamyar; Marx, Daniel; Sharma, Roohani; Spoerhase, Joachim. In Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS’23). 2023.
  • Mind the Gap: Edge Facility Location Problems in Theory and Practice. Beck, Moritz; Spoerhase, Joachim; Storandt, Sabine. In Proc. 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM’23), Vol. 13947, pp. 321–334. 2023.
  • Independent Set in $k$-Claw-Free Graphs: Conditional $\chi$-Boundedness and the Power of {LP/SDP} Relaxations. Chalermsook, Parinya; Gadekar, Ameet; Khodamoradi, Kamyar; Spoerhase, Joachim. In Proc. International Workshop on Approximation and Online Algorithms (WAOA’23). 2023.
2022[ to top ]
  • Coloring Mixed and Directional Interval Graphs. Gutowski, Grzegorz; Mittelst{{ä}}dt, Florian; Rutter, Ignaz; Spoerhase, Joachim; Wolff, Alexander; Zink, Johannes. In Proc. 30th International Symposium Graph Drawing and Network Visualization (GD’22), Vol. 13764, pp. 418–431. 2022.
  • Hypergraph Representation via Axis-Aligned Point-Subspace Cover. Firman, Oksana; Spoerhase, Joachim. In Proc. 16th International Conference and Workshops on Algorithms and Computation (WALCOM’22), Vol. 13174, pp. 328–339. 2022.
2021[ to top ]
  • On Minimum Generalized Manhattan Connections. Antoniadis, Antonios; Capretto, Margarita; Chalermsook, Parinya; Damerius, Christoph; Kling, Peter; Nölke, Lukas; Obscura, Nidia; Spoerhase, Joachim. In Proc. 17th Algorithms and Data Structures Symposium (WADS’21), Vol. 12808, pp. 85–100. 2021.
  • Consistent Simplification of Polyline Tree Bundles. Bosch, Yannick; Schäfer, Peter; Spoerhase, Joachim; Storandt, Sabine; Zink, Johannes. In Proc. 27th International Computing and Combinatorics Conference (COCOON’21). 2021.
2020[ to top ]
  • Approximating Node-Weighted k-MST on Planar Graphs. Byrka, Jarosław; Lewandowski, Mateusz; Spoerhase, Joachim. In Theory of Computing Systems. 2020.
  • A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs. Beyer, Stephan; Chimani, Markus; Spoerhase, Joachim. In Proc. 26th International Computing and Combinatorics Conference (COCOON’20). 2020.
  • Simplification of Polyline Bundles. Spoerhase, Joachim; Storandt, Sabine; Zink, Johannes. In Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT’20). 2020.
  • PTAS for Steiner Tree on Map Graphs. Byrka, Jaroslaw; Lewandowski, Mateusz; Meesum, Syed Mohammad; Spoerhase, Joachim; Uniyal, Sumedha. In Proc. 14th Latin American Theoretical Informatics Symposium (LATIN’20). 2020.
2019[ to top ]
  • A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints. Mizrachi, Eyal; Schwartz, Roy; Spoerhase, Joachim; Uniyal, Sumedha. In Proc. 46th International Colloquium on Automata, Languages and Programming (ICALP’19). 2019.
2018[ to top ]
  • New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness. Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim. In Mathematical Programming, 171(1-2), pp. 433–461. 2018.
  • Approximating the Generalized Minimum {Manhattan} Network Problem. Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander. In Algorithmica, 80(4), pp. 1170–1190. 2018.
  • An Improved Approximation Algorithm for Knapsack Median Using Sparsification. Byrka, Jaros{\l}aw; Pensyl, Thomas; Rybicki, Bartosz; Spoerhase, Joachim; Srinivasan, Aravind; Trinh, Khoa. In Algorithmica, 80(4), pp. 1093–1114. 2018.
  • Approximation Schemes for Geometric Coverage Problems. Chaplick, Steven; De, Minati; Ravsky, Alexander; Spoerhase, Joachim. In Proc. 26th Annual European Symposium on Algorithms (ESA’18), Vol. 112, pp. 17:1–17:15. 2018.
  • Stabbing Rectangles by Line Segments -- How Decomposition Reduces the Shallow-Cell Complexity. Chan, Timothy M.; van Dijk, Thomas C.; Fleszar, Krzysztof; Spoerhase, Joachim; Wolff, Alexander. In Proc. 29th International Symposium on Algorithms and Computation (ISAAC’18). 2018.
  • Approximating Node-Weighted k-{MST} on Planar Graphs. Byrka, Jaros{\l}aw; Lewandowski, Mateusz; Spoerhase, Joachim. In Proc. 16th Workshop on Approximation and Online Algorithms (WAOA’18). 2018.
  • Constant-Factor Approximation for Ordered k-Median. Byrka, Jaroslaw; Sornat, Krzysztof; Spoerhase, Joachim. In Proc. 50th Annual ACM Symposium on the Theory of Computing (STOC’18), pp. 620–631. 2018.
2017[ to top ]
  • Improved Approximation Algorithms for Box Contact Representations. Bekos, Michael A.; van Dijk, Thomas C.; Fink, Martin; Kindermann, Philipp; Kobourov, Stephen G.; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander. In Algorithmica, 77(3), pp. 902–920. 2017.
2016[ to top ]
  • New Algorithms for Disjoint Paths Based on Tree-Likeness. Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim. In Proc. 24th European Symposium on Algorithms (ESA ’16), pp. 42:1–42:17. 2016.
2015[ to top ]
  • Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. Knauer, Martin; Spoerhase, Joachim. In Algorithmica, 71(4), pp. 797–811. 2015.
  • Specialized Heuristics for the Controller Placement Problem in Large Scale {SDN} Networks. Lange, Stanislav; Gebert, Steffen; Spoerhase, Joachim; Rygielski, Piotr; Zinner, Thomas; Kounev, Samuel; Tran{-}Gia, Phuoc. In Proc. 27th International Teletraffic Congress (ITC’15), pp. 210–218. 2015.
  • Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems. Byrka, Jarosław; Fleszar, Krzysztof; Rybicki, Bartosz; Spoerhase, Joachim. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 2015.
  • Colored Non-Crossing Euclidean Steiner Forest. Bereg, Sergey; Fleszar, Krzysztof; Kindermann, Philipp; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander. In Proc. 26th International Symposium on Algorithms and Computation (ISAAC’15), pp. 429–441. 2015.
  • Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees. Chimani, Markus; Spoerhase, Joachim. In Proc. 32nd Symp. Theoretical Aspects of Computer Science (STACS’15). 2015.
  • An Improved Approximation Algorithm for Knapsack Median Using Sparsification. Byrka, Jaroslaw; Pensyl, Thomas; Rybicki, Bartosz; Spoerhase, Joachim; Srinivasan, Aravind; Trinh, Khoa. In Proc. 23rd Annual European Symposium on Algorithms (ESA’15), pp. 275–287. 2015.
  • Approximating Spanning Trees with Few Branches. Chimani, Markus; Spoerhase, Joachim. In Theory Comput. Syst., 56(1), pp. 181–196. 2015.
  • Approximating Minimum Manhattan Networks in Higher Dimensions. Das, Aparna; Gansner, Emden R.; Kaufmann, Michael; Kobourov, Stephen G.; Spoerhase, Joachim; Wolff, Alexander. In Algorithmica, 71(1), pp. 36–52. 2015.
2014[ to top ]
  • {Including Energy Efficiency Aspects in Multi-Layer Optical Network Design}. Gebert, Steffen; Hock, David; Hartmann, Matthias; Spoerhase, Joachim; Zinner, Thomas; Tran-Gia, Phuoc. In 5th International Conference on Communications and Electronics ({ICCE} 2014). Da Nang, Vietnam, 2014.
  • Improved Approximation Algorithms for Box Contact Representations. Bekos, Michael A.; van Dijk, Thomas C.; Fink, Martin; Kindermann, Philipp; Kobourov, Stephen G.; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander. In Proc. 22th Annual European Symposium on Algorithms (ESA’14), pp. 87–99. 2014.
2013[ to top ]
  • Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation. Fink, Martin; Haunert, Jan-Henrik; Spoerhase, Joachim; Wolff, Alexander. In IEEE Transactions on Visualization and Computer Graphics. 2013.
  • Approximating the Generalized Minimum {M}anhattan Network Problem. Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander. In Proc. 24th Int. Symp. Alg. and Comp. (ISAAC’13), Vol. 8283, pp. 722–732. 2013.
2012[ to top ]
  • Algorithms for Labeling Focus Regions. Fink, Martin; Haunert, Jan-Henrik; Schulz, Andr{é}; Spoerhase, Joachim; Wolff, Alexander. In IEEE Trans. Vis. Comput. Graph., 18(12), pp. 2583–2592. 2012.
  • Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. Fink, Martin; Haunert, Jan-Henrik; Mchedlidze, Tamara; Spoerhase, Joachim; Wolff, Alexander. In Proc. 6th International Workshop Algorithms and Computation (WALCOM’12), pp. 186–197. 2012.
  • Approximating Spanning Trees with Few Branches. Chimani, Markus; Spoerhase, Joachim. In Proc. 10th Workshop on Approximation and Online Algorithms (WAOA’12), pp. 30–41. 2012.
2011[ to top ]
  • Maximum Betweenness Centrality: Approximability and Tractable Cases. Fink, Martin; Spoerhase, Joachim. In Proc. 5th Workshop on Algorithms and Computation (WALCOM’11), pp. 9–20. 2011.
  • Approximating Minimum Manhattan Networks in Higher Dimensions. Das, Aparna; Gansner, Emden R.; Kaufmann, Michael; Kobourov, Stephen G.; Spoerhase, Joachim; Wolff, Alexander. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA’11), Vol. 6942, pp. 49–60. 2011.
  • Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs. Schwartges, Nadine; Spoerhase, Joachim; Wolff, Alexander. In Proc. 9th Workshop on Approximationand Online Algorithms (WAOA’11). 2011.
2010[ to top ]
  • Relaxed Voting and Competitive Location under Monotonous Gain Functions on Trees. Spoerhase, Joachim; Wirth, Hans-Christoph. In Discrete Applied Mathematics, 158(4), pp. 361–373. 2010.
  • An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems. Spoerhase, Joachim. In Proc. 21st International Symposium on Algorithms and Computation (ISAAC’10), pp. 440–450. 2010.
  • Competitive and Voting Location. Technical Report (PhD dissertation), . Spoerhase, Joachim. PhD dissertation. Universität Würzburg, 2010.
2009[ to top ]
  • An {O(n (log n)^2 / log log n)} algorithm for the single maximum coverage location or the {(1,X_p)}-medianoid problem on trees. Spoerhase, Joachim; Wirth, Hans-Christoph. In Information Processing Letters, 109(8), pp. 391–394. 2009.
  • Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. Knauer, Martin; Spoerhase, Joachim. In Proc. 11th Algorithms and Data Structures Symposium (WADS’09), pp. 459–470. 2009.
  • Optimally Computing all Solutions of {S}tackelberg with Parametric Prices and of General Monotonous Gain Functions on a Tree. Spoerhase, Joachim; Wirth, Hans-Christoph. In Journal of Discrete Algorithms, 7(2), pp. 256–266. 2009.
  • (r,p)-Centroid problems on Paths and Trees. Spoerhase, Joachim; Wirth, Hans-Christoph. In Theoretical Computer Science, 410(47--49), pp. 5128–5137. 2009.
2008[ to top ]
  • Approximating (r,p)-centroid on a path. Spoerhase, Joachim; Wirth, Hans-Christoph. In Proc. 7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW’08). 2008.
2007[ to top ]
  • Security Score, Plurality Solution, and {N}ash Equilibrium in Multiple Location Problems. Spoerhase, Joachim; Wirth, Hans-Christoph. In 20th European Chapter on Combinatorial Optimization (ECCO’07). 2007.
  • Relaxed Voting and Competitive Location on Trees under Monotonuous Gain Functions. Spoerhase, Joachim; Wirth, Hans-Christoph. In 6th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW’07). 2007.
  • Multiple Voting Location and Single Voting Location on Trees. Noltemeier, Hartmut; Spoerhase, Joachim; Wirth, Hans-Christoph. In European Journal of Operational Research, 181(2), pp. 654–667. 2007.