piwik-script

Deutsch Intern
    Chair of Computer Science I - Algorithms, Complexity, and Knowledge-Based Systems

    Publications (by type)

    Journal Articles

    • Das, A., Fleszar, K., Kobourov, S., Spoerhase, J., Veeramoni, S., Wolff, A.: Approximating the Generalized Minimum Manhattan Network Problem. Algorithmica. 80, 1170--1190 (2018).
       
    • Byrka, J., Pensyl, T., Rybicki, B., Spoerhase, J., Srinivasan, A., Trinh, K.: An Improved Approximation Algorithm for Knapsack Median Using Sparsification. Algorithmica. 80, 1093--1114 (2018).
       
    • Fleszar, K., Mnich, M., Spoerhase, J.: New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness. Mathematical Programming. 171, 433--461 (2018).
       
    • Bekos, M.A., van Dijk, T.C., Fink, M., Kindermann, P., Kobourov, S.G., Pupyrev, S., Spoerhase, J., Wolff, A.: Improved Approximation Algorithms for Box Contact Representations. Algorithmica. 77, 902--920 (2017).
       
    • Das, A., Gansner, E.R., Kaufmann, M., Kobourov, S.G., Spoerhase, J., Wolff, A.: Approximating Minimum Manhattan Networks in Higher Dimensions. Algorithmica. 71, 36--52 (2015).
       
    • Chimani, M., Spoerhase, J.: Approximating Spanning Trees with Few Branches. Theory Comput. Syst. 56, 181--196 (2015).
       
    • Knauer, M., Spoerhase, J.: Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. Algorithmica. 71, 797--811 (2015).
       
    • Fink, M., Haunert, J.-H., Spoerhase, J., Wolff, A.: Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation. IEEE Transactions on Visualization and Computer Graphics. (2013).
       
    • Fink, M., Haunert, J.-H., Schulz, A., Spoerhase, J., Wolff, A.: Algorithms for Labeling Focus Regions. IEEE Trans. Vis. Comput. Graph. 18, 2583-2592 (2012).
       
    • Spoerhase, J., Wirth, H.-C.: Relaxed Voting and Competitive Location under Monotonous Gain Functions on Trees. Discrete Applied Mathematics. 158, 361--373 (2010).
       
    • Spoerhase, J., Wirth, H.-C.: 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. Information Processing Letters. 109, 391--394 (2009).
       
    • Spoerhase, J., Wirth, H.-C.: (r,p)-Centroid problems on Paths and Trees. Theoretical Computer Science. 410, 5128--5137 (2009).
       
    • Spoerhase, J., Wirth, H.-C.: Optimally Computing all Solutions of Stackelberg with Parametric Prices and of General Monotonous Gain Functions on a Tree. Journal of Discrete Algorithms. 7, 256--266 (2009).
       
    • Noltemeier, H., Spoerhase, J., Wirth, H.-C.: Multiple Voting Location and Single Voting Location on Trees. European Journal of Operational Research. 181, 654--667 (2007).
       

    Conference Articles

    • Mizrachi, E., Schwartz, R., Spoerhase, J., Uniyal, S.: A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints. Proc. 46th International Colloquium on Automata, Languages and Programming (ICALP'19) (2019).
       
    • Byrka, J., Lewandowski, M., Spoerhase, J.: Approximating Node-Weighted k-MST on Planar Graphs. Proc. 16th Workshop on Approximation and Online Algorithms (WAOA'18) (2018).
       
    • Chaplick, S., De, M., Ravsky, A., Spoerhase, J.: Approximation Schemes for Geometric Coverage Problems. Proc. 26th Annual European Symposium on Algorithms (ESA'18). p. 17:1--17:15 (2018).
       
    • Byrka, J., Sornat, K., Spoerhase, J.: Constant-Factor Approximation for Ordered k-Median. Proc. 50th Annual ACM Symposium on the Theory of Computing (STOC'18). p. 620--631 (2018).
       
    • Chan, T.M., van Dijk, T.C., Fleszar, K., Spoerhase, J., Wolff, A.: Stabbing Rectangles by Line Segments -- How Decomposition Reduces the Shallow-Cell Complexity. Proc. 29th International Symposium on Algorithms and Computation (ISAAC'18) (2018).
       
    • Fleszar, K., Mnich, M., Spoerhase, J.: New Algorithms for Disjoint Paths Based on Tree-Likeness. Proc. 24th European Symposium on Algorithms (ESA '16). p. 42:1--42:17 (2016).
       
    • Byrka, J., Fleszar, K., Rybicki, B., Spoerhase, J.: Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA'15) (2015).
       
    • Lange, S., Gebert, S., Spoerhase, J., Rygielski, P., Zinner, T., Kounev, S., Tran-Gia, P.: Specialized Heuristics for the Controller Placement Problem in Large Scale SDN Networks. Proc. 27th International Teletraffic Congress (ITC'15). p. 210--218 (2015).
       
    • Bereg, S., Fleszar, K., Kindermann, P., Pupyrev, S., Spoerhase, J., Wolff, A.: Colored Non-Crossing Euclidean Steiner Forest. Proc. 26th International Symposium on Algorithms and Computation (ISAAC'15). p. 429--441 (2015).
       
    • Byrka, J., Pensyl, T., Rybicki, B., Spoerhase, J., Srinivasan, A., Trinh, K.: An Improved Approximation Algorithm for Knapsack Median Using Sparsification. Proc. 23rd Annual European Symposium on Algorithms (ESA'15). p. 275--287 (2015).
       
    • Chimani, M., Spoerhase, J.: Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees. Proc. 32nd Symp. Theoretical Aspects of Computer Science (STACS'15) (2015).
       
    • Bekos, M.A., van Dijk, T.C., Fink, M., Kindermann, P., Kobourov, S.G., Pupyrev, S., Spoerhase, J., Wolff, A.: Improved Approximation Algorithms for Box Contact Representations. Proc. 22th Annual European Symposium on Algorithms (ESA'14). p. 87--99 (2014).
       
    • Gebert, S., Hock, D., Hartmann, M., Spoerhase, J., Zinner, T., Tran-Gia, P.: Including Energy Efficiency Aspects in Multi-Layer Optical Network Design. 5th International Conference on Communications and Electronics (ICCE 2014). , Da Nang, Vietnam (2014).
       
    • Das, A., Fleszar, K., Kobourov, S., Spoerhase, J., Veeramoni, S., Wolff, A.: Approximating the Generalized Minimum Manhattan Network Problem. Proc. 24th Int. Symp. Alg. and Comp. (ISAAC'13). p. 722--732 (2013).
       
    • Chimani, M., Spoerhase, J.: Approximating Spanning Trees with Few Branches. Proc. 10th Workshop on Approximation and Online Algorithms (WAOA'12). pp. 30-41 (2012).
       
    • Fink, M., Haunert, J.-H., Mchedlidze, T., Spoerhase, J., Wolff, A.: Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. Proc. 6th International Workshop Algorithms and Computation (WALCOM'12). pp. 186-197 (2012).
       
    • Schwartges, N., Spoerhase, J., Wolff, A.: Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs. Proc. 9th Workshop on Approximationand Online Algorithms (WAOA'11) (2011).
       
    • Das, A., Gansner, E.R., Kaufmann, M., Kobourov, S.G., Spoerhase, J., Wolff, A.: Approximating Minimum Manhattan Networks in Higher Dimensions. Proceedings of the 19th Annual European Symposium on Algorithms (ESA'11). pp. 49-60 (2011).
       
    • Fink, M., Spoerhase, J.: Maximum Betweenness Centrality: Approximability and Tractable Cases. Proc. 5th Workshop on Algorithms and Computation (WALCOM'11). pp. 9-20 (2011).
       
    • Spoerhase, J.: 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 (2010).
       
    • Knauer, M., Spoerhase, J.: Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. Proc. 11th Algorithms and Data Structures Symposium (WADS'09). pp. 459-470 (2009).
       
    • Spoerhase, J., Wirth, H.-C.: Approximating (r,p)-centroid on a path. Proc. 7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW'08) (2008).
       
    • Spoerhase, J., Wirth, H.-C.: Security Score, Plurality Solution, and Nash Equilibrium in Multiple Location Problems. 20th European Chapter on Combinatorial Optimization (ECCO'07) (2007).
       
    • Spoerhase, J., Wirth, H.-C.: Relaxed Voting and Competitive Location on Trees under Monotonuous Gain Functions. 6th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW'07) (2007).
       

    Dissertation

    • Spoerhase, J.: Competitive and Voting Location, http://nbn-resolving.de/urn:nbn:de:bvb:20-opus-52978, (2010).