Zur Hauptnavigation / To main navigation

Zur Sekundärnavigation / To secondary navigation

Zum Inhalt dieser Seite / To the content of this page

Hauptnavigation / Main Navigation

Sekundärnavigation / Secondary navigation

Research

Inhaltsbereich / Content

Research of Sven O. Krumke

My research interests include but are not limited to:

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

Publications

This list may be out of date. If you are searching for a particular paper, please contact me.

Books

Authors      S. O. Krumke, H. Noltemeier
TitleGraphentheorische Konzepte und Algorithmen, 3
PublishedB.G. Teubner, 2012

TitleOnline Optimization of Large Scale Systems
EditorsM. Grötschel and S. O. Krumke and J. Rambau
PublishedSpringer, 2001

Journals

Authors      S. O. Krumke
TitleOn a Generalization of the $p$-Center Problem
JournalInformation Processing Letters, 56:2 (1995) 67-71
Files PDF [195 kB]  

Authors      S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
TitleBicriteria Compact Location Problems
JournalStudies in Locational Analysis, 10 (1996) 37-51
Files PDF [190 kB]  

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

Authors      S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
TitleCompact Location Problems
JournalTheoretical Computer Science, 181:2 (1997) 379-404
Files PDF [364 kB]  

Authors      S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe, K. U. Drangmeister
TitleModifying Networks to obtain low cost subgraphs
JournalTheoretical Computer Science, 203:1 (1998) 91-121
Files PDF [517 kB]  

Authors      S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, H.-C. Wirth
TitleImproving Spanning Trees by Upgrading Nodes
JournalTheoretical Computer Science, 221:1--2 (1999) 139-155
Files PDF [275 kB]  

Authors      S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, H. C. Wirth
TitleImproving Minimum Cost Spanning Trees by Upgrading Nodes
JournalJournal of Algorithms, 33:1 (1999) 92-111
Files PDF [249 kB]  

Authors      S. Schwarz, S. O. Krumke
TitleOn Budget Constrained Flow Improvement
JournalInformation Processing Letters, 66:6 (1998) 291-297
Files PDF [227 kB]  

Authors      S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi
TitleApproximation Algorithms for Certain Network Improvement Problems
JournalJournal of Combinatorial Optimization, 2 (1998) 257-288
Files PDF [373 kB]  

Authors      S. O. Krumke, M. V. Marathe, S. S. Ravi
TitleModels and Approximation Algorithms for Channel Assignment in Radio Networks
JournalWireless Networks, 7:6 (2001) 575-584

Authors      S. O. Krumke, H.-C. Wirth
TitleOn the Minimum Label Spanning Tree Problem
JournalInformation Processing Letters, 66:2 (1998) 81-85
Files PDF [165 kB]  

Authors      S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi, H.-C. Wirth
TitleUpgrading Bottleneck Constrained Forests
JournalDiscrete Applied Mathematics, 108:1--2 (2001) 129-142
Files PDF [240 kB]  

Authors      H. Noltemeier, H.-C. Wirth, S. O. Krumke
TitleNetwork Design and Network Improvement
JournalACM Computing Surveys, 31:3 (1999)
Files PDF [154 kB]  

Authors      M. Blom, S. O. Krumke, W. E. de Paepe, L. Stougie
TitleThe Online-TSP Against Fair Adversaries
JournalInforms Journal on Computing, 13:2 (2001) 138-148
Files PDF [216 kB]  

Authors      G. Konjevod, S. O. Krumke, M. V. Marathe
TitleBudget Constrained Minimum Cost Connected Medians
JournalJournal of Discrete Algorithms, 2:4 (2004) 453-469
Files PDF [170 kB]  

Authors      D. Hauptmeier, S. O. Krumke, J. Rambau, H.-C. Wirth
TitleEuler is standing in line
JournalDiscrete Applied Mathematics, 113 (2001) 87-107
Files PDF [315 kB]  

Authors      S. O. Krumke, W. E. de Paepe, D. Poensgen, L. Stougie
TitleNews from the Online Traveling Repairman
JournalTheoretical Computer Science, 295:1-3 (2003) 279-294
Files PDF [273 kB]  
See alsoKrumke+etal:OLTRP:TCS:erratum  

Authors      S. O. Krumke, W. E. de Paepe, D. Poensgen, L. Stougie
TitleErratum to News from the online traveling repairman
JournalTheoretical Computer Science, 352:1-3 (2006) 347-348
See alsoKrumke+etal:OLTRP:TCS  

Authors      S. O. Krumke, J. Rambau
TitleProbieren geht über Studieren? Entscheidungshilfen für kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik
Journalat - Automatisierungstechnik, 12 (2002) 568-575
Files PDF [386 kB]  

Authors      A. Coja-Oghlan, S. O. Krumke, T. Nierhoff
TitleA hard dial-a-ride problem that is easy on average
JournalJournal on Scheduling, 8:3 (2005) 197-210
Files PDF [142 kB]  

Authors      A. Coja-Oghlan, S. O. Krumke, T. Nierhoff
TitleA heuristic for the Stacker Crane Problem on trees which is almost surely exact
JournalJournal of Algorithms, 61:1 (2006) 1-19
Files PDF [159 kB]  
See alsoKrumke+etal:Avg-Case-Darp:ISAAC2003  

Authors      S. Gutiérrez, S. O. Krumke, N. Megow, T. Vredeveld
TitleHow to whack moles
JournalTheoretical Computer Science, 361:2 (2006) 329-341
Files PDF [220 kB]  

Authors      B. Hiller, S. O. Krumke, J. Rambau
TitleReoptimization gaps versus model errors in online-dispatching of service units for ADAC
JournalDiscrete Applied Mathematics, 154:13 (2006) 1897-1907
Files PDF [227 kB]  

Authors      M. Grötschel, S. O. Krumke, J. Rambau
TitleWo bleibt der Aufzug?
JournalOR News, 5 (1999) 11-13

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

Authors      M. Grötschel, S. O. Krumke, J. Rambau
TitleOnline Optimization of Complex Transportation Systems
EditorsM. Grötschel and S. O. Krumke and J. Rambau
BooktitleOnline Optimization of Large Scale Systems
PublishedSpringer, 2001, 705-729
See alsoGroetschel+Krumke+Rambau:DFG-Book:2001  

Authors      M. Grötschel, S. O. Krumke, J. Rambau, T. Winter, U. T. Zimmermann
TitleCombinatorial Online Optimization in Real Time
EditorsM. Grötschel and S. O. Krumke and J. Rambau
BooktitleOnline Optimization of Large Scale Systems
PublishedSpringer, 2001, 679-704
See alsoGroetschel+Krumke+Rambau:DFG-Book:2001  

Authors      C. Burch, R. Carr, S. O. Krumke, M. V. Marathe, C. Phillips, E. Sundberg
TitleA Decomposition-Based Pseudoapproximation Algorithm for Network Flow Inhibition
EditorsD.L. Woodruff
BooktitleNetwork Interdiction and Stochastic Integer Programming
PublishedKluwer Academic Press, 2003, 51-68
Files PDF [193 kB]  

Authors      S. O. Krumke, D. Räbiger, R. Schrader
TitleSemi-Preemptive Routing on Trees
JournalDiscrete Applied Mathematics, 156:17 (2008) 3298-3304
Files PDF [161 kB]  

Authors      S. Westphal, S. O. Krumke
TitlePruning in Column Generation for service vehicle dispatching
JournalAnnals of Operations Research, 159:1 (2008) 355-371
Files PDF [220 kB]  

Authors      S. O. Krumke, S. Saliba, T. Vredeveld, S. Westphal
TitleApproximation Algorithms for a vehicle routing problem
JournalMathematical Methods of Operations Research, 68:2 (2008) 333-359
Files PDF [245 kB]  
See alsoKrumke+etal:OR2006  

Authors      S. O. Krumke, A. Schwahn, R. van Stee, S. Westphal
TitleA monotone approximation algorithm for scheduling with precedence constraints
JournalOperations Research Letters, 36 (2008) 247-249
Files PDF [92 kB]  

Authors      S. Westphal, S. O. Krumke, R. van Stee
TitleOnline Job Admission
EditorsS. S. Ravi and Sandeep K. Shukla
BooktitleFundamental Problems in Computing
PublishedSpringer, 2009, 437-456
Files PDF [297 kB]  

Authors      S. O. Krumke, W. E. de Paepe, L. Stougie, J. Rambau
TitleBincoloring
JournalTheoretical Computer Science, 407:1--3 (2008) 231-241
Files PDF [245 kB]  
See alsoKrumke+etal:Bincoloring  

Authors      I. Fink, S. O. Krumke, S. Westphal
TitleNew lower bounds for online $k$-server routing problems
JournalInformation Processing Letters, 109:11 (2009) 563-567
Files PDF [138 kB]  

Authors      E. Gassner, J. Hatzl, S. O. Krumke, H. Sperber, G. J. Woeginger
TitleHow hard is it to find extreme Nash equilibria in congestion games?
JournalTheoretical Computer Science, 410:47--49 (2009) 4989-4999
Files PDF [573 kB]  

Authors      L. Epstein, S. O. Krumke, A. Levin, H. Sperber
TitleSelfish Bincoloring
JournalJournal of Combinatorial Optimization, 22 (2011) 531-548

Authors      E. Gassner, J. Hatzl, S. O. Krumke, S. Saliba
TitleClever or Smart: Strategies for the online target date assignment problem
JournalDiscrete Applied Mathematics, 158:1 (2010) 71-79
Files PDF [246 kB]  

Authors      C. Thielen, S. O. Krumke
TitleTruthful Mechanisms for Selfish Routing and Two-Parameter Agents
JournalTheory of Computing Systems, 49:1 (2011) 196-223
Files PDF [824 kB]  

Authors      C. Thielen, S. O. Krumke
TitleMinimum Cost Flows with Minimum Quantities
JournalInformation Processing Letters, 111:11 (2011) 533-537

Authors      C. Thielen, S. O. Krumke, S. Westphal
TitleInterval Scheduling on Related Machines
JournalComputers and Operations Research, 38:12 (2011) 1836-1844

Authors      S. O. Krumke, S. Westphal, A. Taudes
TitleOnline Scheduling of Weighted Equal-Length Jobs with Hard Deadlines on Parallel Machines
JournalComputers and Operations Research, 38:8 (2011) 1103-1108

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

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

Authors      S. O. Krumke, C. Zeck
TitleGeneralized Max Flow in Series-Parallel Graphs
JournalDiscrete Optimization, 10:2 (2013) 155-162

Authors      S. O. Krumke, C. Thielen
TitleThe Generalized Assignment Problem with Minimum Quantities
JournalEuropean Journal of Operations Research, 228:1 (2013) 46-55
Files PDF [242 kB]  

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

Authors      Th. L. Werth, H. Sperber, S. O. Krumke
TitleComputation of equilibria and the price of anarchy in bottleneck congestion games
JournalCentral European Journal of Operations Research, 22:4 (2014) 687-712

Authors      Th. L. Werth, M. Holzhauser, S. O. Krumke
TitleAtomic routing in a deterministic queuing model
JournalOperations Research Perspectives, 1:1 (2014) 18-41

Authors      Th. L. Werth, S. Büttner, S. O. Krumke
TitleRobust Bottleneck Routing Games
JournalNetworks, (2015)

Refereed Conference Proceedings

Authors      V. Radhakrishnan, S. O. Krumke, M. V. Marathe, D. J. Rosenkrantz, S. S. Ravi
TitleCompact Location Problems
BooktitleProceedings of the 13th Conference on Software Technology and Theoretical Computer Science, Bombay, India
PublishedLecture Notes in Computer Science 761, Springer, 1993, 238-247
Files PDF [252 kB]  

Authors      S. O. Krumke
TitleOn the Convergence of a Modified Barrier Function Method for Convex Quadratic and Linear Programming
BooktitleProceedings of the Third International Conference on Industrial and Applied Mathematics, Hamburg, Germany
Published1995
Files PDF [114 kB]  

Authors      S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
TitleCompact Location Problems with Budget and Communication Constraints
BooktitleProceedings of the 1st International Conference on Computing and Combinatorics
PublishedLecture Notes in Computer Science 959, Springer, 1995, 510-519
Files PDF [222 kB]  

Authors      S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
TitleComplexity and Approximability of some Bicriteria Location Problems
BooktitleProceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science , Aachen, Germany
PublishedLecture Notes in Computer Science 1017, Springer, 1995, 73-87
Files PDF [258 kB]  

Authors      S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe, K. U. Drangmeister
TitleModifying Networks to Obtain Low Cost Trees
BooktitleProceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science , Cadenabbia, Italy
PublishedLecture Notes in Computer Science 1197, Springer, 1996, 293-307
Files PDF [265 kB]  

Authors      S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, H.-C. Wirth
TitleImproving Spanning Trees by Upgrading Nodes
BooktitleProceedings of the 24th International Colloquium on Automata, Languages and Programming
PublishedLecture Notes in Computer Science 1256, 1997, 281-291
Files PDF [242 kB]  

Authors      S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi
TitleNetwork Improvement Problems
EditorsP. M. Pardalos and D. Du
BooktitleNetwork Design: Connectivity and Facilities Location
PublishedAMS-DIMACS Volume Series in Discrete Mathematics and Theoretical Computer Science 40, American Mathematical Society, 1998, 247-268
Files PDF [202 kB]  

Authors      S. O. Krumke, H. Noltemeier, R. Ravi, S. Schwarz, H.-C. Wirth
TitleFlow Improvement and Flows with Fixed Costs
BooktitleProceedings of the International Conference on Operations Research (OR'98)
PublishedSpringer, 1998, 158-167
Files PDF [208 kB]  

Authors      N. Ascheuer, M. Grötschel, S. O. Krumke, J. Rambau
TitleCombinatorial Online Optimization
BooktitleProceedings of the International Conference of Operations Research (OR'98)
PublishedSpringer, 1998, 21-37

Authors      S. O. Krumke, M. V. Marathe, S. S. Ravi
TitleApproximation Algorithms for Channel Assignment in Radio Networks
BooktitleSecond International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Dallas, Texas
Published1998
Files PDF [235 kB]  
See alsoKrumke+etal:Mobicom98:Journal  

Authors      S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi, H.-C. Wirth
TitleUpgrading Bottleneck Constrained Forests
BooktitleProceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science, Smolenice Castle, Slovak Republic
PublishedLecture Notes in Computer Science 1517, 1998, 215-226
Files PDF [234 kB]  
See alsoKrumke+etal:DAM:WG98  

Authors      D. Hauptmeier, S. O. Krumke, J. Rambau, H.-C. Wirth
TitleEuler is standing in line
BooktitleProceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science, Ascona, Switzerland
PublishedLecture Notes in Computer Science 1665, Springer, 1999, 42-54
Files PDF [253 kB]  
See alsoHauptmeier+etal:DARP-DAM  

Authors      M. Grötschel, D. Hauptmeier, S. O. Krumke, J. Rambau
TitleSimulation Studies for the Online Control of an Automated Pallet Transportation System
Year2000

Authors      M. Blom, S. O. Krumke, W. E. de Paepe, L. Stougie
TitleThe Online-TSP Against Fair Adversaries
BooktitleProceedings of the 4th Italian Conference on Algorithms and Complexity
PublishedLecture Notes in Computer Science 1767, Springer, 2000, 137-149
Files PDF [199 kB]  
See alsoKrumke+etal:fair-adversary:journal  

Authors      D. Hauptmeier, S. O. Krumke, J. Rambau
TitleThe Online Dial-a-Ride Problem under Reasonable Load
BooktitleProceedings of the 4th Italian Conference on Algorithms and Complexity
PublishedLecture Notes in Computer Science 1767, Springer, 2000, 125-136
Files PDF [210 kB]  

Authors      N. Ascheuer, S. O. Krumke, J. Rambau
TitleOnline Dial-a-Ride Problems: Minimizing the Completion Time
BooktitleProceedings of the 17th International Symposium on Theoretical Aspects of Computer Science
PublishedLecture Notes in Computer Science 1770, Springer, 2000, 639-650
Files PDF [220 kB]  

Authors      G. Konjevod, S. O. Krumke, M. V. Marathe
TitleBudget Constrained Minimum Cost Connected Medians
BooktitleProceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, Konstanz, Germay
PublishedLecture Notes in Computer Science 1928, Springer, 2000, 267-278
See alsoKrumke+etal:WG2000:JDA  

Authors      S. O. Krumke, W. E. de Paepe, D. Poensgen, L. Stougie
TitleNews from the Online Traveling Repairman
BooktitleProceedings of the 26th International Symposium on Mathematical Foundations of Computer Science
PublishedLecture Notes in Computer Science 2136, 2001, 487-499
Files PDF [164 kB]  
See alsoKrumke+etal:OLTRP:TCS  Krumke+etal:OLTRP:TCS:erratum  

Authors      S. O. Krumke, W. E. de Paepe, L. Stougie, J. Rambau
TitleOnline Bincoloring
BooktitleProceedings of the 9th Annual European Symposium on Algorithms
PublishedLecture Notes in Computer Science 2161, 2001, 74-84
Files PDF [216 kB]  

Authors      S. Fuhrmann, S. O. Krumke, H.-C. Wirth
TitleMultiple Hotlink Assignment
BooktitleProceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science
PublishedLecture Notes in Computer Science 2204, Springer, 2001, 189-200
Files PDF [222 kB]  

Authors      S. O. Krumke, M. Lipmann, W. de Paepe, D. Poensgen, J. Rambau, L. Stougie, G. J. Woeginger
TitleHow to cut a cake almost fairly
BooktitleProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms
Published2002, 263-264
Files PDF [137 kB]  

Authors      S. O. Krumke, D. Poensgen
TitleOnline Call Admission in Optical Networks with Larger Wavelength Demands
BooktitleProceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science
PublishedLecture Notes in Computer Science 2573, Springer, 2002, 333-344
Files PDF [158 kB]  

Authors      S. O. Krumke, M. V. Marathe, D. Poensgen, S. S. Ravi, H.-C. Wirth
TitleBudgeted Maximum Graph Coverage
BooktitleProceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science
PublishedLecture Notes in Computer Science 2573, Springer, 2002, 321-332
Files PDF [255 kB]  

Authors      S. O. Krumke, J. Rambau, L. M. Torres
TitleReal-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows
BooktitleProceedings of the 10th Annual European Symposium on Algorithms
PublishedLecture Notes in Computer Science 2461, Springer, 2002, 637-648
Files PDF [134 kB]  

Authors      S. O. Krumke, L. Laura, M. Lipmann, A. Marchetti-Spaccamela, W. E. de Paepe, D. Poensgen, L. Stougie
TitleNon-Abusiveness Helps: An $O(1)$-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem
BooktitleProceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization
PublishedLecture Notes in Computer Science 2462, Springer, 2002, 200-214
Files PDF [173 kB]  

Authors      R. Hülsermann, M. Jäger, S. O. Krumke, D. Poensgen, J. Rambau, A. Tuchscherer
TitleExperimental Study of Routing Algorithms in Optical Networks
BooktitleProceedings of the 7th IFIP Working Conference on Optical Network Design & Modelling
PublishedKluwer Academic Press, 2003

Authors      A. Coja-Oghlan, S. O. Krumke, T. Nierhoff
TitleScheduling a server on a caterpillar network - a probabilistic analysis
BooktitleProceedings of the 6th Workshop on Models and Algorithms for Planning and Scheduling Problems
Published2003, 48-50
See alsoKrumke+etal:MAPSP-ZR  Krumke+etal:MAPSP03:journal  

Authors      A. Coja-Oghlan, S. O. Krumke, T. Nierhoff
TitleA heuristic for the Stacker Crane Problem on trees which is almost surely exact
BooktitleProceedings of the 14th International Symposium on Algorithms and Computation
PublishedLecture Notes in Computer Science 2906, Springer, 2003, 605-614
Files PDF [134 kB]  

Authors      S. O. Krumke, N. Megow, T. Vredeveld
TitleHow to whack moles
BooktitleProceedings of the 1st Workshop on on Approximation and Online Algorithms
PublishedLecture Notes in Computer Science 2909, Springer, 2003, 192-205
Files PDF [182 kB]  
See alsoKrumke+etal:Whack-a-Mole:journal  

Authors      S. O. Krumke, R. Liu, E. L. Lloyd, M. V. Marathe, R. Ramanathan, S. S. Ravi
TitleTopology Control Problems Under Symmetric and Asymmetric Power Thresholds
BooktitleProceedings of the International Conference on Ad hoc and Wireless Networks
PublishedLecture Notes in Computer Science 2865, Springer, 2003, 187-198
Files PDF [382 kB]  

Authors      B. Hiller, S. O. Krumke, J. Rambau
TitleReoptimization gaps versus model errors in online-dispatching of service units
BooktitleProceedings of the Latin-American Conference on Combinatorics, Graphs and Algorithms
PublishedElectronic Notes in Discrete Mathematics 18, 2004, 157-163
Files PDF [129 kB]  
See alsoKrumke+etal:LACGA04:journal  

Authors      E. Gassner, S. O. Krumke
TitleDeterministic Online Optical Call Admission Revisited
BooktitleProceedings of the 3rd Workshop on on Approximation and Online Algorithms
PublishedLecture Notes in Computer Science 3879, Springer, 2005, 190-202
Files PDF [157 kB]  

Authors      S. O. Krumke, W. E. de Paepe, D. Poensgen, M. Lipmann, A. Marchetti-Spaccamela, L. Stougie
TitleOn Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem
BooktitleProceedings of the 3rd Workshop on on Approximation and Online Algorithms
PublishedLecture Notes in Computer Science 3879, Springer, 2005, 258-269
Files PDF [213 kB]  

Authors      S. Heinz, S. O. Krumke, N. Megow, J. Rambau, A. Tuschscherer, T. Vredeveld
TitleThe Online Target Date Assignment Problem
BooktitleProceedings of the 3rd Workshop on on Approximation and Online Algorithms
PublishedLecture Notes in Computer Science 3879, Springer, 2005, 230-243
Files PDF [180 kB]  

Authors      S. Westphal, S. O. Krumke
TitleImproved Pruning in Column Generation of a Vehicle Routing Problem
BooktitleProceedings of the 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications
Published2005, 705-722
Files PDF [160 kB]  
See alsoWestphal+Krumke:matching-pruning:journal  

Authors      S. O. Krumke, S. Saliba, T. Vredeveld, S. Westphal
TitleApproximation of a Real-World Vehicle Dispatching Problem
BooktitleInternational Conference on Operations Research
Published2006, 181

Authors      K. Bauer, Th. Fischer, S. O. Krumke, K. Gerhardt, S. Westphal, P. Merz
TitleImproved Construction Heuristics and Local Search for the Routing and Wavelength Assignment Problem
BooktitleProceedings of EvoCOP 2008 - Eight European Conference on Evolutionary Computation in Combinatorial Optimisation
PublishedLecture Notes in Computer Science 4972, Springer, 2008, 158-169
Files PDF [258 kB]  

Authors      S. O. Krumke, P. Merz, T. Nonner, K. Rupp
TitleDistributed Approximation Algorithms for Finding $2$-Edge-Connected Subgraphs
BooktitlePrinciples of Distributed Systems
PublishedLecture Notes in Computer Science 4878, Springer, 2007, 159-173
Files PDF [232 kB]  

Authors      E. Gassner, J. Hatzl, S. O. Krumke, H. Sperber, G. J. Woeginger
TitleHow hard is it to find extreme Nash equilibria in congestion games?
BooktitleProceedings of the 4th International Workshop on Internet and Network Economics
PublishedLecture Notes in Computer Science 5385, Springer, 2008, 82-93
Files PDF [493 kB]  
See alsoGassner+etal:WINE2008:journal  

Authors      C. Thielen, S. O. Krumke
TitleA General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints
BooktitleProceedings of the 4th Workshop on on Approximation and Online Algorithms
PublishedLecture Notes in Computer Science 5426, Springer, 2008, 105-118
Files PDF [529 kB]  

Authors      N. Hansen, S. O. Krumke
TitleThe complexity of integrating timetabling and vehicle scheduling
BooktitleProceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems
Published2009

Authors      N. Hansen, S. O. Krumke
TitleIntegrating timetabling and vehicle scheduling
BooktitleProceedings of the 23rd European Conference on Operational Research
Published2009

Authors      C. Thielen, S. O. Krumke
TitleTruthful Mechanisms for Selfish Routing and Two-Parameter Agents
BooktitleProceedings of the 2nd International Symposium on Algorithmic Game Theory
PublishedLecture Notes in Computer Science 5814, 2009, 36-47

Authors      C. Thielen, S. O. Krumke
TitleComplexity of Strong Implementability
BooktitleProceedings of the 4th Athens Colloqium on Algorithms and Complexity
PublishedElectronic Proceedings in Computer Science 4, 2009, 1-12

Authors      B. Engels, S. O. Krumke, R. Schrader, C. Zeck
TitleInteger Flow with Multipliers: The Special Case of Multipliers 1 and 2
BooktitleProceedings of the 8th Cologne Twente Workshop on Graphs and Combinatorial Optimization
Published2009, 239-243

Authors      S. Saliba, S. O. Krumke, B. Hiller, A. Tuchscherer
TitleRandomized online algorithms for the dynamic multi-period routing problem
BooktitleProceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems
Published2009

Authors      S. O. Krumke, C. Thielen
TitleStrong Implementation of Social Choice Functions in Dominant Strategies
EditorsV. Conitzer and Jörg Rothe
BooktitleProceedings of the 3rd International Workshop on Computational Social Choice
Published2010, 319-330

Authors      J. Frasch, S. O. Krumke, S. Westphal
TitleMIP formulations for Flowshop Scheduling with Limited Buffers
BooktitleProceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems
PublishedLecture Notes in Computer Science 6595, Springer, 2011, 127-138

Authors      S. O. Krumke, C. Thielen, S. Westphal
TitleInterval Scheduling on Related Machines: Complexity and Online Algorithms
BooktitleProceedings of the 10th Workshop on Models and Algorithms for Planning and Scheduling Problems
Published2011

Authors      N. Leithäuser, I. Schüle, S. O. Krumke
TitleOptimierte Abstimmung der Umsteigebeziehungen im ungetakteten ÖPNV unter Berücksichtigung der Umlaufplanung
EditorsD. C. Mattfeld and S. Robra-Bissantz
BooktitleMultikonferenz Wirtschaftsinformatik 2012
Published2012

Authors      N. Leithäuser, S. O. Krumke, M. Merkert
TitleApproximating Infeasible 2VPI-Systems
BooktitleProceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science
PublishedLecture Notes in Computer Science 7551, Springer, 2012, 225-236

Authors      S. O. Krumke, A. Quilliot, A. Wagler, J.-Th. Wegener
TitleModels and Algorithms for Carsharing Systems and Related Problems
BooktitleProceedings of the VII Latin-American Algorithms, Graphs, and Optimization Symposium
PublishedElectronic Notes in Discrete Mathematics 44, 2013, 201-206

Authors      S. O. Krumke, F. D. Schwahn, C. Thielen
TitleBeing Negative Makes Life NP-hard (for Product Sellers)
BooktitleProceedings of the 7th International Conference on Fun with Algorithms
PublishedLecture Notes in Computer Science 8496, Springer, 2014, 277-288

Authors      S. O. Krumke, A. Quilliot, A. Wagler, J.-Th. Wegener
TitleRelocation in Carsharing Systems using Flows in Time-Expanded Networks
BooktitleProceedings of the 5th Annual International Conference on Software Engineering & Applications
PublishedLecture Notes in Computer Science 8504, Springer, 2014, 87-98

Authors      P. Halffmann, S. O. Krumke, A. Quilliot, A. Wagler, J.-Th. Wegener
TitleOn the Online Min-Wait Relocation Problem
BooktitleProceedings of the VIII Latin-American Algorithms, Graphs, and Optimization Symposium
PublishedElectronic Notes in Discrete Mathematics, 2015

Preprints and Technical Reports

Authors      S. O. Krumke, J. Valenta
TitleFinding Tree-2-Spanners
NumberUniversity of Würzburg, 131, 1995
Files PDF [296 kB]  

Authors      S. O. Krumke, H. Noltemeier, M. V. Marathe, R. Ravi, S. S. Ravi
TitleImproving Steiner Trees of a Network under Multiple Constraints
NumberLos Alamos National Laboratory, LA-UR 96-1374, 1996
Files PDF [454 kB]  

Authors      S. O. Krumke, H. Noltemeier, M. V. Marathe, S. S. Ravi
TitleNode Weighted Upgrading Problems
NumberLos Alamos National Laboratory, LA-UR 96-1467, 1996
Files PDF [301 kB]  

Authors      H. Noltemeier, S. O. Krumke
TitleOn low cost irredundant kernels of weighted digraphs
NumberUniversity of Würzburg, Germany, 1996

Authors      S. O. Krumke, H. Noltemeier, S. Schwarz, H.-C. Wirth
TitleFlow Improvement and Flows with Fixed Costs
NumberUniversity of Würzburg, 1998

Authors      N. Ascheuer, M. Grötschel, S. O. Krumke, J. Rambau
TitleCombinatorial Online Optimization
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, SC 98-24, 1998

Authors      N. Ascheuer, S. O. Krumke, J. Rambau
TitleCompetitive Scheduling of Elevators
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, SC 98-34, 1998

Authors      D. Hauptmeier, S. O. Krumke, J. Rambau, H.-C. Wirth
TitleEuler is standing in line
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, SC 99-06, 1999

Authors      D. Hauptmeier, S. O. Krumke, J. Rambau
TitleThe Online Dial-a-Ride Problem under Reasonable Load
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, SC 99-08, 1999
See alsoKrumke+etal:resload  

Authors      M. Grötschel, D. Hauptmeier, S. O. Krumke, J. Rambau
TitleSimulation Studies for the Online Dial-a-Ride Problem
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, SC 99-09, 1999

Authors      M. Blom, S. O. Krumke, W. E. de Paepe, L. Stougie
TitleThe Online-TSP Against Fair Adversaries
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, 00-09, 2000
See alsoKrumke+etal:fair-adversary  Krumke+etal:fair-adversary:journal  

Authors      M. Grötschel, S. O. Krumke, J. Rambau
TitleWo bleibt der Aufzug?
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, SC 99-29, 1999
See alsoGroetschel+etal:Aufzug-ornews  

Authors      S. O. Krumke
TitleNews from the Online Traveling Repairman
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, 00-08, 2000
See alsoKrumke+etal:OLTRP  Krumke+etal:OLTRP:TCS  

Authors      S. O. Krumke, J. Rambau, S. Weider
TitleAn Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, 00-53, 2000

Authors      S. O. Krumke, J. Rambau, L. M. Torres
TitleRealtime-Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, 01-22, 2001

Authors      S. O. Krumke, J. Rambau, L. M. Torres
TitleOnline Dispatching of Automobile in Real-Time
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, 02-18, 2002

Authors      S. O. Krumke, J. Rambau
TitleProbieren geht über Studieren? Entscheidungshilfen für kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, 02-05, 2002

Authors      A. Coja-Oghlan, S. O. Krumke, T. Nierhoff
TitleAverage Case Analysis of a Hard Dial-a-Ride Problem
NumberKonrad-Zuse-Zentrum für Informationstechnik Berlin, 2003
See alsoKrumke+etal:MAPSP03:journal  

Thesises

Authors      S. O. Krumke
TitleEine modifizierte Barrieremethode für konvexe quadratische Optimierungsprobleme
Year1994
Files PDF [1913 kB]  

Authors      S. O. Krumke
TitleOn the approximability of location and network design problems
Year1996
Files PDF [1169 kB]  

Authors      S. O. Krumke
TitleOnline Optimization: Competitive Analysis and Beyond
Year2002
Files PDF [1810 kB]