NOTICE: This page is out of date, since I am now at the Konrad-Zuse-Zentrum für Informationstechnik Berlin. An updated version can be found at my new home page http://www.zib.de/krumke. My new email-address is krumke@zib.de.
My main area of research is the design of approximation algorithms for NP-hard problems. So far, I have focussed mainly on location problems and network design problems, which have been the topic of my thesis.
I am also interested in efficient graph algorithms.
Below you can find information about my publications (including links to my coauthors and my teaching (only in German). I appreciate any
comments and criticism
Publications sorted by dateWhen you click on a file name your Web browser may start a postscript viewer or may ask for a filename to save. In the latter case, pick a name ending in .ps.gz, then gunzip that name to get a .ps file for printing or previewing. If you have trouble, or need hardcopy, my email is krumke@informatik.uni-wuerzburg.de
S.O. Krumke, H. Noltemeier, M.V. Marathe, S.S. Ravi and K.U. Drangmeister. Modifying Networks to Obtain Low Cost Subgraphs. Theoretical Computer Science (to appear)
S.O. Krumke, M.V. Marathe, H. Noltemeier, V. Radhakrishnan, S.S. Ravi and D.J. Rosenkrantz. Compact Location Problems. Theoretical Computer Science, 1997, 181(2), pages 379-404
C. Mauckner, H. Noltemeier and S.O. Krumke. Finding Placement Sequences and Bin-Locations for Pick and Place Robots. Studies in Locational Analysis, issue 10, pages 67-89, Semper Excellens, October 1996.
S.O. Krumke, H. Noltemeier, S.S. Ravi and M.V. Marathe. Bicriteria Compact Location Problems. Studies in Locational Analysis, issue 10, pages 37-51, Semper Excellens, October 1996.
S.O. Krumke. On a Generalisation of the p-Center Problem.Volume 56 of Information Processing Letters, pages 67-71. Elsevier, 1995.
S.O. Krumke, M.V. Marathe, H. Noltemeier, R. Ravi, and S.S. Ravi. Network Improvement Problems. In AMS-DIMACS Volume Series on Discrete Mathematics and Theoretical Computer Science: Workshop on Network Design and Location Theory, 1998 (to appear).
S.O. Krumke, M.V. Marathe, H. Noltemeier, R. Ravi, S.S. Ravi, R. Sundaram and H.-C. Wirth. Improving Spanning Trees by Upgrading Nodes. In Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97), volume 1256 of Lecture Notes in Computer Science, pages 281-291 Springer, 1997.
S.O. Krumke, H. Noltemeier, M.V. Marathe, S.S. Ravi and K.U. Drangmeister. Modifying Networks to Obtain Low Cost Trees. In Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'96), Cadenabbia, Italy, volume 1197 of Lecture Notes in Computer Science, pages 293-307. Springer, 1996.
C. Mauckner, H. Noltemeier and S.O. Krumke. Finding Placement Sequences and Bin-Locations for Pick and Place Robots. In Proceedings of the Eigth Meeting of the EURO Working Group on Locational Analysis, Lambrecht, Germany, 1995.
S.O. Krumke, H. Noltemeier, S.S. Ravi and M.V. Marathe. Bicriteria Compact Location Problems.In Proceedings of the Eigth Meeting of the EURO Working Group on Locational Analysis, Lambrecht, Germany, 1995.
S.O. Krumke, H. Noltemeier, S.S. Ravi and M.V. Marathe. Compact Location Problems with Budget and Communication Constraints. In Proceedings of the 1st International Conference on Computing and Combinatorics (Cocoon'95), X'ian, China, volume 959 of Lecture Notes in Computer Science, pages 510-519. Springer, 1995.
S.O. Krumke, H. Noltemeier, S.S. Ravi and M.V. Marathe. Complexity and Approximability of Some Bicriteria Location Problems. In Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'95), Aachen, Germany, volume 1017 of Lecture Notes in Computer Science, pages 73-87. Springer, 1995.
S.O. Krumke. On the Convergence of a Modified Barrier Function Method for Convex Quadratic and Linear Programming.In Proceedings of the Third International Conference on Industrial and Applied Mathematics (ICIAM'95), Hamburg, Germany.
V. Radhakrishnan, S.O. Krumke, M.V. Marathe, D.J. Rosenkrantz and S.S. Ravi. Compact Location Problems.In Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTCS'93), Bombay, India, 1993 volume 761 of Lecture Notes in Computer Science, pages 238-247. Springer, 1993.
S.O. Krumke. On the Approximability of Location and Network Design Problems. Dissertation, University of Würzburg, 1996.
S.O. Krumke, H. Noltemeier, M.V. Marathe and S.S. Ravi. Node Weighted Upgrading Problems.Technical Report LA-UR 96-1467, Los Alamos National Laboratory, Los Alamos, NM, 1996
S.O. Krumke, H. Noltemeier, M.V. Marathe, S.S. Ravi and R. Ravi. Improving Steiner Trees of a Network under Multiple Constraints. Technical Report LA-UR 96-1467, Los Alamos National Laboratory, Los Alamos, NM, 1996
S.O. Krumke and J. Valenta. Finding Tree-2-Spanners.Technical Report 131, University of Würzburg, December 1995.
S.O. Krumke. Eine modifizierte Barrieremethode für konvexe quadratische Optimierungsprobleme. Master's Thesis, University of Würzburg, 1994.
S.O. Krumke, M.V. Marathe, H. Noltemeier, R. Ravi and S.S. Ravi. Approximation Algorithms of Certain Network Improvement Problems. November 1997. Submitted for publication.
C. Burch, S.O. Krumke, M.V. Marathe, C. Phillips and E. Sundberg. Multicriteria Approximation through Decomposition November 1997. Submitted for publication.
S.O. Krumke and H.-C. Wirth. On the Minimum Label Spanning Tree Problem. Würzburg, November 1997. Submitted for publication.
S. Schwarz and S.O. Krumke. On Budget Constrained Flow Improvement. Würzburg, September 1997. Submitted for publication.
Teaching (available only in German)Sven O. Krumke (krumke@informatik.uni-wuerzburg.de)