Optimization Group

Prof. Dr. Sven O. Krumke

Address

Paul-Ehrlich-Straße
Gebäude 14 , Raum 434
67663 Kaiserslautern

Postfach 3049
67653 Kaiserslautern

Contact

Tel.: +49 631 205 4808
Fax: +49 631 205 4737 (working group)
Fax: +49 631 205 4427 (Dean's Office)
E-Mail: sven.krumke@math.rptu.de

Currently, I am also the Dean of the Department of Mathematics at RPTU. For all matters concerning my work as dean, please visit the dean's office website.

Research Interests

My research interests are:

  • Combinatorial Optimization
  • Approximation Algorithms
  • Online Algorithms
  • Computational Complexity
  • Algorithmic Game Theory
  • Graph Theory and its applications

Research Projects

I am currently working on the following research projects:

ONE PLAN: Optimization of Emergency Rescue in Rhineland-Palatinate

Current Lectures

In the current semester I offer the following lectures:

Integer Programming: Polyhedral Theory and Algorithms

Reading Course

Seminar "Mathematische Optimierung"

Proseminar "Modellierung in der Wirtschaftsmathematik"

Curriculum Vitae

  • since 2004: Full Professor in the Department of Mathematics at the University of Kaiserslautern-Landau
     
  • 2002: Habilitation, Technical University Berlin
    Thesis: Online Optimization: Competitive Analysis and Beyond
    Committee: Martin Grötschel, Susanne Albers, Gerhard J. Woeginger

     
  • 1998-2004: Postdoc Researcher at the Konrad Zuse Center for Information Technology Berlin (ZIB)
     
  • 1997: Doctorate (Dr.rer.nat.), University of Würzburg
    Thesis: On the Approximability of Location and Network Design Problems
    Committee: Hartmut Noltemeier, Josef Stoer

     
  • 1994-1998: Research Assistant at the Department of Computer Science at the University of Würzburg
     
  • 1994: Master in Mathematics (Diploma), University of Würzburg
    Diploma Thesis: A Modified Barrier Method for Convex Quadratic Optimization Problems
    Advisor: Josef Stoer

     
  • 1992-1993: Exchange student at the Department of Computer Science at the State University of New York at Albany, partly funded by the German-American Fulbright Commission.
  • 1988-1994: Study of Mathematics and Computer Science at the University of Würzburg

Publications

  • N. Leithäuser, D. Adelhütte, K. Braun, C. Büsing, M. Comis, T. Gersing, S. Johann, A. M. C. A. Koster, S. O. Krumke, F. Liers, E. Schmidt, J. Schneider, M. Streicher, S. Tschuppik, S. Wrede
    Decision-support systems for ambulatory care, including pandemic requirements: using mathematically optimized solutions
    BMC Medical Informatics and Decision Making 22 (2022)

  • O. Bachtler, S. O. Krumke
    Towards Obtaining a 3-Decomposition from a Perfect Matching
    The Electronic Journal of Combinatorics 29 (2022)

  • N. Leithaeuser, J. Schneider, S. Johann, S. Krumke, M. Streicher, E. Schmidt, S. Scholz
    Quantifying Covid19-Vaccine Location Strategies For Germany
    BMC Health Services Research 21 (2021)

  • S. O. Krumke, H. L. Minh
    Robust absolute single machine makespan scheduling-location problem on trees
    Operations Research Letters 48, pp. 29-32 (2020)

  • S. O. Krumke, H. L. Minh, O. Bachtler
    Robust single machine makespan scheduling with release date uncertainty
    Operations Research Letters 48, pp. 816 - 819 (2020)

  • S. O. Krumke, E. Schmidt, M. Streicher
    Robust Multicovers with Budgeted Uncertainty
    European Journal of Operations Research (2018)

  • S. Krumke, C. Thielen, P. Weinschenk, S. Westphal
    Full Implementation of Social Choice Functions in Dominant Strategies
    International Journal of Game Theory, pp. 1-26 (2018)

  • M. Holzhauser, S. O. Krumke
    A Generalized Approximation Framework for Fractional Network Flow and Packing Problems
    Mathematical Methods of Operations Research 87, pp. 19-50 (2018)

  • N. Halman, M. Holzhauser, S. O. Krumke
    An FPTAS for the knapsack problem with parametric weights
    Operations Research Letters 46, pp. 487-491 (2018)

  • M. Holzhauser, S. O. Krumke, C. Thielen
    On the Complexity and Approximability of Budget-Constrained Minimum Cost Flows
    Information Processing Letters 126, pp. 24-29 (2017)

  • M. Holzhauser, S. O. Krumke, C. Thielen
    A Network Simplex Method for the Budget-Constrained Minimum Cost Flow Problem
    European Journal of Operational Research 259, pp. 864-872 (2017)

  • M. Holzhauser, S. O. Krumke, C. Thielen
    Maximum Flows in Generalized Processing Networks
    Journal of Combinatorial Optimization 33, pp. 1226-1256 (2017)

  • M. Holzhauser, S. O. Krumke
    An FPTAS for the parametric knapsack problem
    Information Processing Letter 126, pp. 43-47 (2017)

  • A. Chassein, S. O. Krumke, C. Thielen
    Capacitated Network Design Games with Weighted Players
    Networks 68, pp. 141-158 (2016)

  • M. Holzhauser, S. O. Krumke, C. Thielen
    Budget-Constrained Minimum Cost Flows
    Journal of Combinatorial Optimization 31, pp. 1720-1745 (2016)

  • P. Halffmann, S. O. Krumke, A. Quilliot, A. K. Wagler, J. Wegener
    On the Online Min-Wait Relocation Problem
    Electronic Notes in Discrete Mathematics 50, pp. 281 - 286 (2015)

  • M. Holzhauser, S. O. Krumke, C. Thielen
    Convex Generalized Flows
    Discrete Applied Mathematics 190-191, pp. 86-99 (2015)

  • T. L. Werth, S. Büttner, S. O. Krumke
    Robust Bottleneck Routing Games
    Networks 66, pp. 57-66 (2015)

  • S. Büttner, S. O. Krumke
    The Canadian Tour Operator Problem on Paths - Tight Bounds and Resource Augmentation
    Journal of Combinatorial Optimization (2015)

  • S. Büttner, S. O. Krumke
    Robust Optimization for Routing Problems on Trees
    TOP: An Official Journal of the Spanish Society of Statistics and Operations Research (2015)

  • L. Turner, D. P. Gross, H. W. Hamacher, S. O. Krumke
    Static and dynamic source locations in undirected networks
    TOP: An Official Journal of the Spanish Society of Statistics and Operations Research 23 (2015)

  • L. Turner, D. P. Groß, H. W. Hamacher, S. O. Krumke
    Rejoinder on: Static and dynamic source locations in undirected networks
    TOP 23, pp. 665-668 (2015)

  • T. L. Werth, H. Sperber, S. O. Krumke
    Computation of equilibria and the price of anarchy in bottleneck congestion games
    Central European Jurnal of Operations Research 22, pp. 687-712 (2014)

  • T. L. Werth, M. Holzhauser, S. O. Krumke
    Atomic routing in a deterministic queuing model
    Operations Research Perspectives 1, pp. 18-41 (2014)

  • S. O. Krumke, C. Thielen
    The Generalized Assignment Problem with Minimum Quantities
    European Journal of Operational Research 228, pp. 46-55 (2013)

  • M. Bender, S. Büttner, S. O. Krumke
    Online delay management on a single train line: beyond competitive analysis
    Public Transport 5, pp. 243-266 (2013)

  • S. O. Krumke, C. Zeck
    Generalized max flow in series--parallel graphs
    Discrete Optimization 10, pp. 155-162 (2013)

  • S. O. Krumke, J. Rambau
    Stability with Uniform Bounds for On-Line Dial-a-Ride Problems under Reasonable Load
    Lecture Notes in Control and Information Sciences 417, pp. 387-412 (2012)

  • S. O. Krumke, C. Thielen, C. Zeck
    Extensions to Online Delay Management on a Single Train Line: New Bounds for Delay Minimization and Profit Maximization
    Mathematical Methods of Operations Research 74, pp. 53-75 (2011)

  • S. O. Krumke, C. Thielen, S. Westphal
    Interval Scheduling on Related Machines
    Computers and Operations Research 38, pp. 1836-1844 (2011)

  • S. O. Krumke, C. Thielen
    Minimum Cost Flows with Minimum Quantities
    Information Processing Letters 111, pp. 533-537 (2011)

  • C. Thielen, S. O. Krumke
    Truthful Mechanisms for Selfish Routing and Two-Parameter Agents
    Theory of Computing Systems 49, pp. 196-223 (2011)

  • L. Epstein, S. O. Krumke, A. Levin, H. Sperber
    Selfish Bincoloring
    Journal of Combinatorial Optimization 22, pp. 531-548 (2011)

  • S. O. Krumke, S. Westphal, A. Taudes
    Online Scheduling of Weighted Equal-Length Jobs with Hard Deadlines on Parallel Machines
    Computers and Operations Research 38, pp. 1103-1108 (2011)

  • E. Gassner, J. Hatzl, S. O. Krumke, S. Saliba
    Clever or Smart: Strategies for the online target date assignment problem
    Discrete Applied Mathematics 158, pp. 71-79 (2010)

  • E. Gassner, J. Hatzl, S. O. Krumke, H. Sperber, G. J. Woeginger
    How hard is it to find extreme Nash equilibria in congestion games?
    Theoretical Computer Science 410, pp. 4989-4999 (2009)

  • I. Fink, S. O. Krumke, S. Westphal
    New lower bounds for online k-server routing problems
    Information Processing Letters 109, pp. 563-567 (2009)

  • S. O. Krumke, W. E. d. Paepe, L. Stougie, J. Rambau
    Bincoloring
    Theoretical Computer Science 407, pp. 231-241 (2008)

  • S. Westphal, S. O. Krumke
    Pruning in Column Generation for service vehicle dispatching
    Annals of Operations Research 159, pp. 355-371 (2008)

  • S. O. Krumke, D. Räbiger, R. Schrader
    Semi-Preemptive Routing on Trees
    Discrete Applied Mathematics 156, pp. 3298-3304 (2008)

  • S. O. Krumke, S. Saliba, T. Vredeveld, S. Westphal
    Approximation Algorithms for a vehicle routing problem
    Mathematical Methods of Operations Research 68, pp. 333-359 (2008)

  • S. O. Krumke, A. Schwahn, R. v. Stee, S. Westphal
    A monotone approximation algorithm for scheduling with precedence constraints
    Operations Research Letters 36, pp. 247-249 (2008)

  • S. O. Krumke, W. E. d. Paepe, D. Poensgen, L. Stougie
    Erratum to News from the online traveling repairman
    Theoretical Computer Science 352, pp. 347-348 (2006)

  • A. Coja-Oghlan, S. O. Krumke, T. Nierhoff
    A heuristic for the Stacker Crane Problem on trees which is almost surely exact
    Journal of Algorithms 61, pp. 1-19 (2006)

  • S. Gutiérrez, S. O. Krumke, N. Megow, T. Vredeveld
    How to whack moles
    Theoretical Computer Science 361, pp. 329-341 (2006)

  • B. Hiller, S. O. Krumke, J. Rambau
    Reoptimization gaps versus model errors in online-dispatching of service units for ADAC
    Discrete Applied Mathematics 154, pp. 1897-1907 (2006)

  • A. Coja-Oghlan, S. O. Krumke, T. Nierhoff
    A hard dial-a-ride problem that is easy on average
    Journal on Scheduling 8, pp. 197-210 (2005)

  • D. Hauptmeier, S. O. Krumke, J. Rambau
    The Online Dial-a-Ride Problem under Reasonable Load
    Theoretical Commputer Science (2004)

  • G. Konjevod, S. O. Krumke, M. V. Marathe
    Budget Constrained Minimum Cost Connected Medians
    Journal of Discrete Algorithms 2, pp. 453-469 (2004)

  • S. O. Krumke, W. E. d. Paepe, D. Poensgen, L. Stougie
    News from the Online Traveling Repairman
    TCS 295, pp. 279-294 (2003)

  • M. Grötschel, S. O. Krumke, J. Rambau, L. M. Torres
    Making the yellow angels fly: Online Dispatching of service vehicles in real time
    SIAM news 35, pp. 10-11 (2002)

  • S. O. Krumke, J. Rambau
    Probieren geht über Studieren? Entscheidungshilfen für kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik
    at - Automatisierungstechnik 12, pp. 568-575 (2002)

  • S. O. Krumke, M. V. Marathe, S. S. Ravi
    Models and Approximation Algorithms for Channel Assignment in Radio Networks
    Wireless Networks 7, pp. 575-584 (2001)

  • S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi, H.-C. Wirth
    Upgrading Bottleneck Constrained Forests
    Discrete Applied Mathematics 108, pp. 129-142 (2001)

  • D. Hauptmeier, S. O. Krumke, J. Rambau, H.-C. Wirth
    Euler is standing in line
    Discrete Applied Mathematics 113, pp. 87-107 (2001)

  • M. Blom, S. O. Krumke, W. E. d. Paepe, L. Stougie
    The Online-TSP Against Fair Adversaries
    Informs Journal on Computing 13, pp. 138-148 (2001)

  • S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, H.-C. Wirth
    Improving Spanning Trees by Upgrading Nodes
    Theoretical Computer Science 221, pp. 139-155 (1999)

  • S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, H. C. Wirth
    Improving Minimum Cost Spanning Trees by Upgrading Nodes
    Journal of Algorithms 33, pp. 92-111 (1999)

  • H. Noltemeier, H.-C. Wirth, S. O. Krumke
    Network Design and Network Improvement
    ACM Computing Surveys 31 (1999)

  • M. Grötschel, S. O. Krumke, J. Rambau
    Wo bleibt der Aufzug?
    OR News, pp. 11-13 (1999)

  • S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe, K. U. Drangmeister
    Modifying Networks to obtain low cost subgraphs
    Theoretical Computer Science 203, pp. 91-121 (1998)

  • S. Schwarz, S. O. Krumke
    On Budget Constrained Flow Improvement
    Information Processing Letters 66, pp. 291-297 (1998)

  • S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi
    Approximation Algorithms for Certain Network Improvement Problems
    Journal of Combinatorial Optimization 2, pp. 257-288 (1998)

  • S. O. Krumke, H.-C. Wirth
    On the Minimum Label Spanning Tree Problem
    Information Processing Letters 66, pp. 81-85 (1998)

  • S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
    Compact Location Problems
    Theoretical Computer Science 181, pp. 379-404 (1997)

  • S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
    Bicriteria Compact Location Problems
    Studies in Locational Analysis 10, pp. 37-51 (1996)

  • C. Mauckner, H. Noltemeier, S. O. Krumke
    Finding Placement Sequences and Bin Locations for Pick and Place Robots
    Studies in Locational Analysis 10, pp. 67-89 (1996)

  • S. O. Krumke
    On a Generalization of the p-Center Problem
    Information Processing Letters 56, pp. 67-71 (1995)
  • Graphentheorische Konzepte und Algorithmen
    S O. Krumke, H. Noltemeier,
    B.G. Teubner, (2012)

  • Online Job Admission
    S. Westphal, S. O. Krumke, R. Stee,
    Fundamental Problems in Computing, Springer, pp. 437-456 (2009)

  • A Decomposition-Based Pseudoapproximation Algorithm for Network Flow Inhibition
    C. Burch, R. Carr, S O. Krumke, M V. Marathe, C. Phillips, E. Sundberg,
    Network Interdiction and Stochastic Integer Programming, Kluwer Academic Press, pp. 51-68 (2003)

  • Online Optimization of Large Scale Systems
    M. Grötschel, S O. Krumke, R. J. (Eds.),
    Springer, (2001)

  • Online Optimization of Complex Transportation Systems
    M. Grötschel, S O. Krumke, J. Rambau,
    Online Optimization of Large Scale Systems, Springer, pp. 705-729 (2001)

  • Combinatorial Online Optimization in Real Time
    M. Grötschel, S O. Krumke, J. Rambau, T. Winter, U T. Zimmermann,
    Online Optimization of Large Scale Systems, Springer, pp. 679-704 (2001)

  • Network Improvement Problems
    S O. Krumke, M V. Marathe, H. Noltemeier, R. Ravi, S S. Ravi,
    Network Design: Connectivity and Facilities Location 40, American Mathematical Society, pp. 247-268 (1998)

  • O. Bachtler, T. Bergner, S. O. Krumke
    Local Certification of Reachability
    Proceedings of the 10th International Network Optimization Conference, pp. 40-44 (2022)

  • L. E. Schäfer, T. Dietz, M. V. Natale, S. Ruzika, S. O. Krumke, C. M. Fonseca
    The Bicriterion Maximum Flow Network Interdiction Problem in s-t-Planar Graphs
    Operations Research Proceedings 2019, pp. 133-139 (2020)

  • M. Jung, D. M. Mathew, C. Weis, W. Norbert, I. Heinrich, M. V. Natale, S. O. Krumke
    ConGen: An Application Specific DRAM Memory Controller Generator
    Proceedings of the Second International Symposium on Memory Systems, pp. 257-267 (2016)

  • P. Halffmann, S. O. Krumke, A. Quilliot, A. K. Wagler, J. Wegener
    On the Online Min-Wait Relocation Problem
    Procedings of 6th International Workshop on Freight Transportation and Logistics (ODYSSEUS 2015), Electronic Notes in Discrete Mathematics (2015)

  • S. O. Krumke, F. D. Schwahn, C. Thielen
    Being Negative Makes Life NP-hard (for Product Sellers)
    Proceedings of the 7th International Conference on Fun with Algorithms (FUN), LNCS (8496), pp. 277-288 (2014)

  • S. O. Krumke, A. Quilliot, A. Wagler, J. Wegener
    Relocation in Carsharing Systems using Flows in Time-Expanded Networks
    Proceedings of the 5th Annual International Conference on Software Engineering & Applications, LNCS (8504), pp. 87-98 (2014)

  • S. O. Krumke, A. Quilliot, A. Wagler, J. Wegener
    Models and Algorithms for Carsharing Systems and Related Problems
    Proceedings of the VII Latin-American Algorithms, Graphs, and Optimization Symposium, Electronic Notes in Discrete Mathematics (44), pp. 201-206 (2013)

  • N. Leithäuser, S. O. Krumke, M. Merkert
    Approximating Infeasible 2VPI-Systems
    Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (7551), pp. 225-236 (2012)

  • N. Leithäuser, I. Schüle, S. O. Krumke
    Optimierte Abstimmung der Umsteigebeziehungen im ungetakteten öPNV unter Berücksichtigung der Umlaufplanung
    Multikonferenz Wirtschaftsinformatik 2012 (2012)

  • S. O. Krumke, C. Thielen, S. Westphal
    Interval Scheduling on Related Machines: Complexity and Online Algorithms
    Proceedings of the 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), pp. 236-238 (2011)

  • J. Frasch, S. O. Krumke, S. Westphal
    MIP formulations for Flowshop Scheduling with Limited Buffers
    Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, LNCS (6595), pp. 127-138 (2011)

  • C. Thielen, S. O. Krumke
    Strong Implementation of Social Choice Function in Dominant Strategies
    Proceedings of the 3rd International Workshop on Computational Social Choice (COMSOC), pp. 319-330 (2010)

  • S. O. Krumke, C. Thielen
    Strong Implementation of Social Choice Functions in Dominant Strategies
    Proceedings of the 3rd International Workshop on Computational Social Choice, pp. 319-330 (2010)

  • C. Thielen, S. O. Krumke
    Truthful Mechanisms for Selfish Routing and Two-Parameter Agents
    Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT), LNCS (5814), pp. 36-47 (2009)

  • C. Thielen, S. O. Krumke
    Complexity of Strong Implementability
    Proceedings of the 4th Athens Colloquium on Algorithms and Complexity (ACAC), EPTCS (4), pp. 1-12 (2009)

  • N. Hansen, S. O. Krumke
    The complexity of integrating timetabling and vehicle scheduling
    Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (2009)

  • N. Hansen, S. O. Krumke
    Integrating timetabling and vehicle scheduling
    Proceedings of the 23rd European Conference on Operational Research (2009)

  • S. Saliba, S. O. Krumke, B. Hiller, A. Tuchscherer
    Randomized online algorithms for the dynamic multi-period routing problem
    Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (2009)

  • B. Engels, S. O. Krumke, R. Schrader, C. Zeck
    Integer Flow with Multipliers: The Special Case of Multipliers 1 and 2
    Proceedings of the 8th Cologne Twente Workshop on Graphs and Combinatorial Optimization, pp. 239-243 (2009)

  • C. Thielen, S. O. Krumke
    A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints
    Proceedings of the 6th Workshop on Approximation and Online Algorithms (WAOA), LNCS (5426), pp. 105-118 (2008)

  • K. Bauer, Th. Fischer, S. O. Krumke, K. Gerhardt, S. Westphal, P. Merz
    Improved Construction Heuristics and Local Search for the Routing and Wavelength Assignment Problem
    Proceedings of EvoCOP 2008 -- Eight European Conference on Evolutionary Computation in Combinatorial Optimisation, LNCS (4972), pp. 158-169 (2008)

  • E. Gassner, J. Hatzl, S. O. Krumke, H. Sperber, G. J. Woeginger
    How hard is it to find extreme Nash equilibria in congestion games?
    Proceedings of the 4th International Workshop on Internet and Network Economics, LNCS (5385), pp. 82-93 (2008)

  • S. O. Krumke, P. Merz, T. Nonner, K. Rupp
    Distributed Approximation Algorithms for Finding 2-Edge-Connected Subgraphs
    Principles of Distributed Systems, LNCS (4878), pp. 159-173 (2007)

  • S. O. Krumke, S. Saliba, T. Vredeveld, S. Westphal
    Approximation of a Real-World Vehicle Dispatching Problem
    International Conference on Operations Research, pp. 181 (2006)

  • E. Gassner, S. O. Krumke
    Deterministic Online Optical Call Admission Revisited
    Proceedings of the 3rd Workshop on Approximation and Online Algorithms, LNCS (3879), pp. 190-202 (2005)

  • S. O. Krumke, W. E. d. Paepe, D. Poensgen, M. Lipmann, A. Marchetti-Spaccamela, L. Stougie
    On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem
    Proceedings of the 3rd Workshop on Approximation and Online Algorithms, LNCS (3879), pp. 258-269 (2005)

  • S. Heinz, S. O. Krumke, N. Megow, J. Rambau, A. Tuschscherer, T. Vredeveld
    The Online Target Date Assignment Problem
    Proceedings of the 3rd Workshop on Approximation and Online Algorithms, LNCS (3879), pp. 230-243 (2005)

  • S. Westphal, S. O. Krumke
    Improved Pruning in Column Generation of a Vehicle Routing Problem
    Proceedings of the 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications, pp. 705-722 (2005)

  • B. Hiller, S. O. Krumke, J. Rambau
    Reoptimization gaps versus model errors in online-dispatching of service units
    Proceedings of the Latin-American Conference on Combinatorics, Graphs and Algorithms, Electronic Notes in Discrete Mathematics (18), pp. 157-163 (2004)

  • R. Hülsermann, M. Jäger, S. O. Krumke, D. Poensgen, J. Rambau, A. Tuchscherer
    Experimental Study of Routing Algorithms in Optical Networks
    Proceedings of the 7th IFIP Working Conference on Optical Network Design & Modelling (2003)

  • A. Coja-Oghlan, S. O. Krumke, T. Nierhoff
    Scheduling a server on a caterpillar network - a probabilistic analysis
    Proceedings of the 6th Workshop on Models and Algorithms for Planning and Scheduling Problems, pp. 48-50 (2003)

  • A. Coja-Oghlan, S. O. Krumke, T. Nierhoff
    A heuristic for the Stacker Crane Problem on trees which is almost surely exact
    Proceedings of the 14th International Symposium on Algorithms and Computation, LNCS (2906), pp. 605-614 (2003)

  • S. O. Krumke, N. Megow, T. Vredeveld
    How to whack moles
    Proceedings of the 1st Workshop on Approximation and Online Algorithms, LNCS (2909), pp. 192-205 (2003)

  • S. O. Krumke, R. Liu, E. L. Lloyd, M. V. Marathe, R. Ramanathan, S. S. Ravi
    Topology Control Problems Under Symmetric and Asymmetric Power Thresholds
    Proceedings of the International Conference on Ad hoc and Wireless Networks, LNCS (2865), pp. 187-198 (2003)

  • S. O. Krumke, M. Lipmann, W. d. Paepe, D. Poensgen, J. Rambau, L. Stougie, G. J. Woeginger
    How to cut a cake almost fairly
    Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 263-264 (2002)

  • S. O. Krumke, D. Poensgen
    Online Call Admission in Optical Networks with Larger Wavelength Demands
    Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (2573), pp. 333-344 (2002)

  • S. O. Krumke, M. V. Marathe, D. Poensgen, S. S. Ravi, H.-C. Wirth
    Budgeted Maximum Graph Coverage
    Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (2573), pp. 321-332 (2002)

  • S. O. Krumke, J. Rambau, L. M. Torres
    Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows
    Proceedings of the 10th Annual European Symposium on Algorithms, LNCS (2461), pp. 637-648 (2002)

  • S. O. Krumke, J. Rambau, L. M. Torres
    Online-Dispatching of Automobile Service Units
    Proceedings of the International Conference of Operations Research (OR2002), pp. 168-173 (2002)

  • S. O. Krumke, L. Laura, M. Lipmann, A. Marchetti-Spaccamela, W. E. d. Paepe, D. Poensgen, L. Stougie
    Non-Abusiveness Helps: An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem
    Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, LNCS (2462), pp. 200-214 (2002)

  • S. O. Krumke, W. E. d. Paepe, D. Poensgen, L. Stougie
    News from the Online Traveling Repairman
    Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, LNCS (2136), pp. 487-499 (2001)

  • S. O. Krumke, W. E. d. Paepe, L. Stougie, J. Rambau
    Online Bincoloring
    Proceedings of the 9th Annual European Symposium on Algorithms, LNCS (2161), pp. 74-84 (2001)

  • S. Fuhrmann, S. O. Krumke, H.-C. Wirth
    Multiple Hotlink Assignment
    Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (2204), pp. 189-200 (2001)

  • M. Blom, S. O. Krumke, W. E. d. Paepe, L. Stougie
    The Online-TSP Against Fair Adversaries
    Proceedings of the 4th Italian Conference on Algorithms and Complexity, LNCS (1767), pp. 137-149 (2000)

  • D. Hauptmeier, S. O. Krumke, J. Rambau
    The Online Dial-a-Ride Problem under Reasonable Load
    Proceedings of the 4th Italian Conference on Algorithms and Complexity, LNCS (1767), pp. 125-136 (2000)

  • N. Ascheuer, S. O. Krumke, J. Rambau
    Online Dial-a-Ride Problems: Minimizing the Completion Time
    Proceedings of the 17th International Symposium on Theoretical Aspects of Computer Science, LNCS (1770), pp. 639-650 (2000)

  • G. Konjevod, S. O. Krumke, M. V. Marathe
    Budget Constrained Minimum Cost Connected Medians
    Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, Konstanz, Germay, LNCS (1928), pp. 267-278 (2000)

  • D. Hauptmeier, S. O. Krumke, J. Rambau, H.-C. Wirth
    Euler is standing in line
    Proceedings of the 25th International Workshop on Graph-Theoretic Concept in Computer Science, Ascona, Switzerland, LNCS (1665), pp. 42-54 (1999)

  • S. O. Krumke, H. Noltemeier, R. Ravi, S. Schwarz, H.-C. Wirth
    Flow Improvement and Flows with Fixed Costs
    Proceedings of the International Conference on Operations Research (OR'98), pp. 158-167 (1998)

  • N. Ascheuer, M. Grötschel, S. O. Krumke, J. Rambau
    Combinatorial Online Optimization
    Proceedings of the International Conference of Operations Research (OR'98), pp. 21-37 (1998)

  • S. O. Krumke, M. V. Marathe, S. S. Ravi
    Approximation Algorithms for Channel Assignment in Radio Networks
    Second International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Dallas, Texas (1998)

  • S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi, H.-C. Wirth
    Upgrading Bottleneck Constrained Forests
    Proceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science, Smolenice Castle, Slovak Republic, LNCS (1517), pp. 215-226 (1998)

  • S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, H.-C. Wirth
    Improving Spanning Trees by Upgrading Nodes
    Proceedings of the 24th International Colloquium on Automata, Languages and Programming, LNCS (1256), pp. 281-291 (1997)

  • S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
    Bicriteria Compact Location Problems
    Recent Advances in Locational Analysis, Studies in Locational Analysis (10), pp. 37-51 (1996)

  • C. Mauckner, H. Noltemeier, S. O. Krumke
    Finding Placement Sequences and Bin Locations for Pick and Place Robots
    Recent Advances in Locational Analysis, Studies in Locational Analysis (10), pp. 67-89 (1996)

  • S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe, K. U. Drangmeister
    Modifying Networks to Obtain Low Cost Trees
    Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science , Cadenabbia, Italy, LNCS (1197), pp. 293-307 (1996)

  • S. O. Krumke
    On the Convergence of a Modified Barrier Function Method for Convex Quadratic and Linear Programming
    Proceedings of the Third International Conference on Industrial and Applied Mathematics, Hamburg, Germany (1995)

  • S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
    Compact Location Problems with Budget and Communication Constraints
    Proceedings of the 1st International Conference on Computing and Combinatorics, LNCS (959), pp. 510-519 (1995)

  • S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
    Complexity and Approximability of some Bicriteria Location Problems
    Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science , Aachen, Germany, LNCS (1017), pp. 73-87 (1995)

  • V. Radhakrishnan, S. O. Krumke, M. V. Marathe, D. J. Rosenkrantz, S. S. Ravi
    Compact Location Problems
    Proceedings of the 13th Conference on Software Technology and Theoretical Computer Science, Bombay, India, LNCS (761), pp. 238-247 (1993)
Go to top