Research outputs
2026
A Broader View on Clustering under Cluster-Aware Norm Objectives
Herold, M. G., Kipouridis, E., & Spoerhase, J. (2026). A Broader View on Clustering under Cluster-Aware Norm Objectives. In Unknown Conference (pp. 758-793). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611978971.30
2025
Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions
Herold, M. G., Nanongkai, D., Spoerhase, J., Varma, N., & Wu, Z. (2025). Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions. In Leibniz International Proceedings in Informatics Lipics Vol. 332. doi:10.4230/LIPIcs.SoCG.2025.56
SIMPLIFICATION OF POLYLINE BUNDLES OF GRAPHS AND TREES
Bosch, Y., Schaefer, P., Spoerhase, J., Storandt, S., & Zink, J. (2025). SIMPLIFICATION OF POLYLINE BUNDLES OF GRAPHS AND TREES. JOURNAL OF COMPUTATIONAL GEOMETRY, 16(1), 203-252. Retrieved from https://www.webofscience.com/
Clustering to Minimize Cluster-Aware Norm Objectives
Herold, M. G., Kipouridis, E., & Spoerhase, J. (2025). Clustering to Minimize Cluster-Aware Norm Objectives. In Unknown Conference (pp. 255-287). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611978322.8
Hypergraph Representation via Axis-Aligned Point-Subspace Cover
Firman, O., & Spoerhase, J. (2025). Hypergraph Representation via Axis-Aligned Point-Subspace Cover. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 27(2). doi:10.46298/dmtcs.11676
2024
Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces
Abbasi, F., Byrka, J., Gadekar, A., Marx, D., Spoerhase, J., Banerjee, S., . . . Sharma, R. (2024). Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces. In Leibniz International Proceedings in Informatics Lipics Vol. 297. doi:10.4230/LIPIcs.ICALP.2024.6
Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter
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, 20(1). doi:10.1145/3632623
SkelEx and BoundEx - Geometrical Framework for Interpretable ReLU Neural Networks
Pukowski, P., Spoerhase, J., & Lu, H. (2024). SkelEx and BoundEx - Geometrical Framework for Interpretable ReLU Neural Networks. In 2024 INTERNATIONAL JOINT CONFERENCE ON NEURAL NETWORKS, IJCNN 2024. doi:10.1109/IJCNN60899.2024.10650882
2023
A Constant-Factor Approximation Algorithm for Reconciliation k-Median
Spoerhase, J., Khodamoradi, K., Riegel, B., Ordozgoiti, B., & Gionis, A. (2023). A Constant-Factor Approximation Algorithm for Reconciliation k-Median. In Proceedings of Machine Learning Research Vol. 206 (pp. 1719-1746).
Coloring Mixed and Directional Interval Graphs
Gutowski, G., Mittelstaedt, F., Rutter, I., Spoerhase, J., Wolff, A., & Zink, J. (2023). Coloring Mixed and Directional Interval Graphs. In Unknown Book (Vol. 13764, pp. 418-431). doi:10.1007/978-3-031-22203-0_30
Independent Set in <i>k</i>-Claw-Free Graphs: Conditional χ-Boundedness and the Power of LP/SDP Relaxations
Chalermsook, P., Gadekar, A., Khodamoradi, K., & Spoerhase, J. (2023). Independent Set in <i>k</i>-Claw-Free Graphs: Conditional χ-Boundedness and the Power of LP/SDP Relaxations. In APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2023 Vol. 14297 (pp. 205-218). doi:10.1007/978-3-031-49815-2_15
Mind the Gap: Edge Facility Location Problems in Theory and Practice
Beck, M., Spoerhase, J., & Storandt, S. (2023). Mind the Gap: Edge Facility Location Problems in Theory and Practice. In ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2023 Vol. 13947 (pp. 321-334). doi:10.1007/978-3-031-25211-2_25
Parameterized Approximation Schemes for Clustering with General Norm Objectives
Abbasi, F., Banerjee, S., Byrka, J., Chalermsook, P., Gadekar, A., Khodamoradi, K., . . . Spoerhase, J. (2023). Parameterized Approximation Schemes for Clustering with General Norm Objectives. In 2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS (pp. 1377-1399). doi:10.1109/FOCS57990.2023.00085
2022
Hypergraph Representation via Axis-Aligned Point-Subspace Cover
Firman, O., & Spoerhase, J. (2022). Hypergraph Representation via Axis-Aligned Point-Subspace Cover. In Unknown Book (Vol. 13174, pp. 328-339). doi:10.1007/978-3-030-96731-4_27
2021
Consistent Simplification of Polyline Tree Bundles
Bosch, Y., Schaefer, P., Spoerhase, J., Storandt, S., & Zink, J. (2021). Consistent Simplification of Polyline Tree Bundles. In Unknown Book (Vol. 13025, pp. 231-243). doi:10.1007/978-3-030-89543-3_20
On Minimum Generalized Manhattan Connections
Antoniadis, A., Capretto, M., Chalermsook, P., Damerius, C., Kling, P., Noelke, L., . . . Spoerhase, J. (2021). On Minimum Generalized Manhattan Connections. In ALGORITHMS AND DATA STRUCTURES, WADS 2021 Vol. 12808 (pp. 85-100). doi:10.1007/978-3-030-83508-8_7
2020
Simplification of polyline bundles
Spoerhase, J., Storandt, S., & Zink, J. (2020). Simplification of polyline bundles. In Leibniz International Proceedings in Informatics Lipics Vol. 162. doi:10.4230/LIPIcs.SWAT.2020.35
Approximating Node-Weighted <i>k</i>-MST on Planar Graphs
Byrka, J., Lewandowski, M., & Spoerhase, J. (2020). Approximating Node-Weighted <i>k</i>-MST on Planar Graphs. THEORY OF COMPUTING SYSTEMS, 64(4), 626-644. doi:10.1007/s00224-020-09965-w
A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs
Beyer, S., Chimani, M., & Spoerhase, J. (2020). A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs. In COMPUTING AND COMBINATORICS (COCOON 2020) Vol. 12273 (pp. 347-359). doi:10.1007/978-3-030-58150-3_28
PTAS for Steiner Tree on Map Graphs
Byrka, J. L., Lewandowski, M., Meesum, S. M., Spoerhase, J., & Uniyal, S. (2020). PTAS for Steiner Tree on Map Graphs. In Unknown Book (Vol. 12118, pp. 3-14). doi:10.1007/978-3-030-61792-9_1
2019
A tight approximation for submodular maximization with mixed packing and covering constraints
Mizrachi, E., Schwartz, R., Spoerhase, J., & Uniyal, S. (2019). A tight approximation for submodular maximization with mixed packing and covering constraints. In Leibniz International Proceedings in Informatics Lipics Vol. 132. doi:10.4230/LIPIcs.ICALP.2019.85
2018
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity
Chan, T. M., van Dijk, T. C., Fleszar, K., Spoerhase, J., & Wolff, A. (2018). Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity. In 29TH INTERNATIONAL SYMPOSIUM ON ALGORITHMS AND COMPUTATION, ISAAC 2018 Vol. 123. doi:10.4230/LIPIcs.ISAAC.2018.61
New algorithms for maximum disjoint paths based on tree-likeness
Fleszar, K., Mnich, M., & Spoerhase, J. (2018). New algorithms for maximum disjoint paths based on tree-likeness. MATHEMATICAL PROGRAMMING, 171(1-2), 433-461. doi:10.1007/s10107-017-1199-3
Approximation schemes for geometric coverage problems
Chaplick, S., De, M., Ravsky, A., & Spoerhase, J. (2018). Approximation schemes for geometric coverage problems. In Leibniz International Proceedings in Informatics Lipics Vol. 112. doi:10.4230/LIPIcs.ESA.2018.17
Brief announcement: Approximation schemes for geometric coverage problems
Chaplick, S., De, M., Ravsky, A., & Spoerhase, J. (2018). Brief announcement: Approximation schemes for geometric coverage problems. In Leibniz International Proceedings in Informatics Lipics Vol. 107. doi:10.4230/LIPIcs.ICALP.2018.107
Constant-Factor Approximation for Ordered k-Median
Byrka, J., Sornat, K., & Spoerhase, J. (2018). Constant-Factor Approximation for Ordered k-Median. In STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (pp. 620-631). doi:10.1145/3188745.3188930
An Improved Approximation Algorithm for Knapsack Median Using Sparsification
Byrka, J., Pensyl, T., Rybicki, B., Spoerhase, J., Srinivasan, A., & Khoa, T. (2018). An Improved Approximation Algorithm for Knapsack Median Using Sparsification. ALGORITHMICA, 80(4), 1093-1114. doi:10.1007/s00453-017-0294-4
Approximating the Generalized Minimum Manhattan Network Problem
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. doi:10.1007/s00453-017-0298-0
Approximating Node-Weighted <i>k</i>-MST on Planar Graphs
Byrka, J., Lewandowski, M., & Spoerhase, J. (2018). Approximating Node-Weighted <i>k</i>-MST on Planar Graphs. In Unknown Book (Vol. 11312, pp. 87-101). doi:10.1007/978-3-030-04693-4_6
2017
Improved Approximation Algorithms for Box Contact Representations
Bekos, M. A., van Dijk, T. C., Fink, M., Kindermann, P., Kobourov, S., Pupyrev, S., . . . Wolff, A. (2017). Improved Approximation Algorithms for Box Contact Representations. ALGORITHMICA, 77(3), 902-920. doi:10.1007/s00453-016-0121-3
2016
New algorithms for maximum disjoint paths based on tree-likeness
Fleszar, K., Mnich, M., & Spoerhase, J. (2016). New algorithms for maximum disjoint paths based on tree-likeness. In Leibniz International Proceedings in Informatics Lipics Vol. 57. doi:10.4230/LIPIcs.ESA.2016.42
2015
Specialized Heuristics for the Controller Placement Problem in Large Scale SDN Networks
Lange, S., Gebert, S., Spoerhase, J., Rygielski, P., Zinner, T., Kounev, S., & Phuoc, T. -G. (2015). Specialized Heuristics for the Controller Placement Problem in Large Scale SDN Networks. In 2015 27TH INTERNATIONAL TELETRAFFIC CONGRESS ITC 27 (pp. 210-218). doi:10.1109/ITC.2015.32
WOS:000350873800002 Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
Knauer, M., & Spoerhase, J. (2015). WOS:000350873800002 Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. ALGORITHMICA, 71(4), 797-811. doi:10.1007/s00453-013-9827-7
Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees
Chimani, M., & Spoerhase, J. (2015). Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees. In 32ND INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2015) Vol. 30 (pp. 238-248). doi:10.4230/LIPIcs.STACS.2015.238
An Improved Approximation Algorithm for Knapsack Median Using Sparsification
Byrka, J., Pensyl, T., Rybicki, B., Spoerhase, J., Srinivasan, A., & Khoa, T. (2015). An Improved Approximation Algorithm for Knapsack Median Using Sparsification. In ALGORITHMS - ESA 2015 Vol. 9294 (pp. 275-287). doi:10.1007/978-3-662-48350-3_24
Approximating Minimum Manhattan Networks in Higher Dimensions
Das, A., Gansner, E. R., Kaufmann, M., Kobourov, S., Spoerhase, J., & Wolff, A. (2015). Approximating Minimum Manhattan Networks in Higher Dimensions. ALGORITHMICA, 71(1), 36-52. doi:10.1007/s00453-013-9778-z
Bi-Factor Approximation Algorithms for Hard Capacitated <i>k</i>-Median Problems
Byrka, J., Fleszar, K., Rybicki, B., & Spoerhase, J. (2015). Bi-Factor Approximation Algorithms for Hard Capacitated <i>k</i>-Median Problems. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 722-736). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973730.49
Colored Non-crossing Euclidean Steiner Forest
Bereg, S., Fleszar, K., Kindermann, P., Pupyrev, S., Spoerhase, J., & Wolff, A. (2015). Colored Non-crossing Euclidean Steiner Forest. In ALGORITHMS AND COMPUTATION, ISAAC 2015 Vol. 9472 (pp. 429-441). doi:10.1007/978-3-662-48971-0_37
2014
Including Energy Efficiency Aspects In Multi-Layer Optical Network Design
Gebert, S., Hock, D., Hartmann, M., Spoerhase, J., Zinner, T., & Tran-Gia, P. (2014). Including Energy Efficiency Aspects In Multi-Layer Optical Network Design. In 2014 IEEE FIFTH INTERNATIONAL CONFERENCE ON COMMUNICATIONS AND ELECTRONICS (ICCE) (pp. 212-217). Retrieved from https://www.webofscience.com/
Approximating Spanning Trees with Few Branches
Chimani, M., & Spoerhase, J. (2015). Approximating Spanning Trees with Few Branches. THEORY OF COMPUTING SYSTEMS, 56(1), 181-196. doi:10.1007/s00224-014-9556-6
Improved Approximation Algorithms for Box Contact Representations
Bekos, M. A., van Dijk, T. C., Fink, M., Kindermann, P., Kobourov, S., Pupyrev, S., . . . Wolff, A. (2014). Improved Approximation Algorithms for Box Contact Representations. In ALGORITHMS - ESA 2014 Vol. 8737 (pp. 87-99). Retrieved from https://www.webofscience.com/
On Monotone Drawings of Trees
Kindermann, P., Schulz, A., Spoerhase, J., & Wolff, A. (2014). On Monotone Drawings of Trees. GRAPH DRAWING (GD 2014), 8871, 488-500. Retrieved from https://www.webofscience.com/
2013
Approximating the Generalized Minimum Manhattan Network Problem
Das, A., Fleszar, K., Kobourov, S., Spoerhase, J., Veeramoni, S., & Wolff, A. (2013). Approximating the Generalized Minimum Manhattan Network Problem. In ALGORITHMS AND COMPUTATION Vol. 8283 (pp. 722-732). Retrieved from https://www.webofscience.com/
Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation
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. doi:10.1109/TVCG.2013.187
Approximating Spanning Trees with Few Branches
Chimani, M., & Spoerhase, J. (2013). Approximating Spanning Trees with Few Branches. In Lecture Notes in Computer Science (pp. 30-41). Springer Berlin Heidelberg. doi:10.1007/978-3-642-38016-7_4
Road segment selection with strokes and stability
van Dijk, T. C., Fleszar, K., Haunert, J. -H., & Spoerhase, J. (2013). Road segment selection with strokes and stability. In Proceedings of the 1st ACM SIGSPATIAL International Workshop on MapInteraction (pp. 72-77). ACM. doi:10.1145/2534931.2534936
2012
Algorithms for Labeling Focus Regions
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. doi:10.1109/TVCG.2012.193
Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs
Schwartges, N., Spoerhase, J., & Wolff, A. (2012). Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs. In Unknown Conference (pp. 77-88). Springer Berlin Heidelberg. doi:10.1007/978-3-642-29116-6_7
Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles
Fink, M., Haunert, J. -H., Mchedlidze, T., Spoerhase, J., & Wolff, A. (2012). Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. In Unknown Conference (pp. 186-197). Springer Berlin Heidelberg. doi:10.1007/978-3-642-28076-4_19
Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles
Fink, M., Haunert, J. -H., Mchedlidze, T., Spoerhase, J., & Wolff, A. (2012). Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. In GRAPH DRAWING Vol. 7034 (pp. 441-+). Retrieved from https://www.webofscience.com/
2011
Approximating Minimum Manhattan Networks in Higher Dimensions
Das, A., Gansner, E. R., Kaufmann, M., Kobourov, S., Spoerhase, J., & Wolff, A. (2011). Approximating Minimum Manhattan Networks in Higher Dimensions. In ALGORITHMS - ESA 2011 Vol. 6942 (pp. 49-60). Retrieved from https://www.webofscience.com/
Maximum Betweenness Centrality: Approximability and Tractable Cases
Fink, M., & Spoerhase, J. (2011). Maximum Betweenness Centrality: Approximability and Tractable Cases. In WALCOM: ALGORITHMS AND COMPUTATION Vol. 6552 (pp. 9-20). Retrieved from https://www.webofscience.com/
2010
An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems
Spoerhase, J. (2010). An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems. In ALGORITHMS AND COMPUTATION, PT I Vol. 6506 (pp. 440-450). Retrieved from https://www.webofscience.com/
Relaxed voting and competitive location under monotonous gain functions on trees
Spoerhase, J., & Wirth, H. -C. (2010). Relaxed voting and competitive location under monotonous gain functions on trees. DISCRETE APPLIED MATHEMATICS, 158(4), 361-373. doi:10.1016/j.dam.2009.05.006
2009
(<i>r</i>, <i>p</i>)-centroid problems on paths and trees
Spoerhase, J., & Wirth, H. -C. (2009). (<i>r</i>, <i>p</i>)-centroid problems on paths and trees. THEORETICAL COMPUTER SCIENCE, 410(47-49), 5128-5137. doi:10.1016/j.tcs.2009.08.020
Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
Knauer, M., & Spoerhase, J. (2009). Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. In ALGORITHMS AND DATA STRUCTURES Vol. 5664 (pp. 459-470). Retrieved from https://www.webofscience.com/
Optimally computing all solutions of Stackelberg with parametric prices and of general monotonous gain functions on a tree
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. doi:10.1016/j.jda.2009.02.004
An <i>O</i> (<i>n</i>(log <i>n</i>)<SUP>2</SUP>/log log <i>n</i>) algorithm for the single maximum coverage location or the (1, <i>X<sub>p</sub></i>)-medianoid problem on trees
Spoerhase, J., & Wirth, H. -C. (2009). An <i>O</i> (<i>n</i>(log <i>n</i>)<SUP>2</SUP>/log log <i>n</i>) algorithm for the single maximum coverage location or the (1, <i>X<sub>p</sub></i>)-medianoid problem on trees. INFORMATION PROCESSING LETTERS, 109(8), 391-394. doi:10.1016/j.ipl.2008.12.009
2008
Approximating (r, p)-Centroid on a path
Spoerhase, J., & Wirth, H. C. (2008). Approximating (r, p)-Centroid on a path. In 7th Cologne Twente Workshop on Graphs and Combinatorial Optimization Ctw 2008 (pp. 193-195).
2007
Multiple voting location and single voting location on trees
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. doi:10.1016/j.ejor.2006.06.039