Publications
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
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) (pp. 1-8). IEEE. doi:10.1109/ijcnn60899.2024.10650882
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), 1-20. doi:10.1145/3632623
2023
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). IEEE. doi:10.1109/focs57990.2023.00085
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., Mittelstädt, F., Rutter, I., Spoerhase, J., Wolff, A., & Zink, J. (2023). Coloring Mixed and Directional Interval Graphs. In Lecture Notes in Computer Science (pp. 418-431). Springer International Publishing. doi:10.1007/978-3-031-22203-0_30
Independent Set in k-Claw-Free Graphs: Conditional $$\chi $$-Boundedness and the Power of LP/SDP Relaxations
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. In Unknown Conference (pp. 205-218). Springer Nature Switzerland. 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 Unknown Conference (pp. 321-334). Springer International Publishing. doi:10.1007/978-3-031-25211-2_25
2022
Hypergraph Representation via Axis-Aligned Point-Subspace Cover
Firman, O., & Spoerhase, J. (2022). Hypergraph Representation via Axis-Aligned Point-Subspace Cover. In Lecture Notes in Computer Science (pp. 328-339). Springer International Publishing. doi:10.1007/978-3-030-96731-4_27
2021
Consistent Simplification of Polyline Tree Bundles
Bosch, Y., Schäfer, P., Spoerhase, J., Storandt, S., & Zink, J. (2021). Consistent Simplification of Polyline Tree Bundles. In Lecture Notes in Computer Science (pp. 231-243). Springer International Publishing. doi:10.1007/978-3-030-89543-3_20
On Minimum Generalized Manhattan Connections
Antoniadis, A., Capretto, M., Chalermsook, P., Damerius, C., Kling, P., Nölke, L., . . . Spoerhase, J. (2021). On Minimum Generalized Manhattan Connections. In Unknown Conference (pp. 85-100). Springer International Publishing. 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 k-MST on Planar Graphs
Byrka, J., Lewandowski, M., & Spoerhase, J. (2020). Approximating Node-Weighted k-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 Unknown Conference (pp. 347-359). Springer International Publishing. doi:10.1007/978-3-030-58150-3_28
PTAS for Steiner Tree on Map Graphs
Byrka, J., Lewandowski, M., Meesum, S. M., Spoerhase, J., & Uniyal, S. (2020). PTAS for Steiner Tree on Map Graphs. In Lecture Notes in Computer Science (pp. 3-14). Springer International Publishing. 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 Leibniz International Proceedings in Informatics, LIPIcs Vol. 123.
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), 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 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 620-631). ACM. doi:10.1145/3188745.3188930
An Improved Approximation Algorithm for Knapsack Median Using Sparsification
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. 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 k-MST on Planar Graphs
Byrka, J., Lewandowski, M., & Spoerhase, J. (2018). Approximating Node-Weighted k-MST on Planar Graphs. In Lecture Notes in Computer Science (pp. 87-101). Springer International Publishing. 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., & Tran-Gia, P. (2015). Specialized Heuristics for the Controller Placement Problem in Large Scale SDN Networks. In 2015 27th International Teletraffic Congress (pp. 210-218). IEEE. doi:10.1109/itc.2015.32
Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
Knauer, M., & Spoerhase, J. (2015). 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 Leibniz International Proceedings in Informatics, LIPIcs 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., & Trinh, K. (2015). An Improved Approximation Algorithm for Knapsack Median Using Sparsification. In Unknown Conference (pp. 275-287). Springer Berlin Heidelberg. 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 Unknown Conference (pp. 429-441). Springer Berlin Heidelberg. 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., & Phuoc Tran-Gia. (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). IEEE. doi:10.1109/cce.2014.6916705
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 Unknown Conference (pp. 87-99). Springer Berlin Heidelberg. doi:10.1007/978-3-662-44777-2_8
On Monotone Drawings of Trees
Kindermann, P., Schulz, A., Spoerhase, J., & Wolff, A. (2014). On Monotone Drawings of Trees. Unknown Journal, 488-500. doi:10.1007/978-3-662-45803-7_41
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 Unknown Conference (pp. 722-732). Springer Berlin Heidelberg. doi:10.1007/978-3-642-45030-3_67
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
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
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 Unknown Conference (pp. 441-442). Springer Berlin Heidelberg. doi:10.1007/978-3-642-25878-7_43
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 Unknown Conference (pp. 49-60). Springer Berlin Heidelberg. doi:10.1007/978-3-642-23719-5_5
Maximum Betweenness Centrality: Approximability and Tractable Cases
Fink, M., & Spoerhase, J. (2011). Maximum Betweenness Centrality: Approximability and Tractable Cases. In Unknown Conference (pp. 9-20). Springer Berlin Heidelberg. doi:10.1007/978-3-642-19094-0_4
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 Unknown Conference (pp. 440-450). Springer Berlin Heidelberg. doi:10.1007/978-3-642-17517-6_39
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
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mrow><mml:mo>(</mml:mo><mml:mi>r</mml:mi><mml:mo>,</mml:mo><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>-centroid problems on paths and trees
Spoerhase, J., & Wirth, H. -C. (2009). <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mrow><mml:mo>(</mml:mo><mml:mi>r</mml:mi><mml:mo>,</mml:mo><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>-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 Unknown Conference (pp. 459-470). Springer Berlin Heidelberg. doi:10.1007/978-3-642-03367-4_40
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 algorithm for the single maximum coverage location or the -medianoid problem on trees
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. 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