Optimization Group

Prof. Dr. Sven O. Krumke

Address

Paul-Ehrlich-Straße
Building: 14
Room: 434
67663 Kaiserslautern

P.O. Box: 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.

Prof. Dr. Sven O. Krumke

Lectures and seminars

During the summer semester 2024 the following lectures and seminars will be offered by me:

I also supervise Bachelor's and Master's theses. If you are interested in this, please contact me by e-mail.

Research Interests

My research interests are:

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

Research projects

RTG 2982: MIMO

Mathematics of Interdisciplinary Multiobjective Optimization

Read more
ONE PLAN

Optimization in emergency rescue in the Rhineland-Palatinate area

Read more

Curriculum Vitae

  • since 2004: Full Professor in the Department of Mathematics at the University of Kaiserslautern-Landau, previously TU Kaiserslautern
     
  • 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)