Approximation algorithms for a vehicle routing problem (2006)
Krumke, Sven O., Saliba, Sleman, Vredeveld, Tjark, Westphal, Stephan
Online Call Admission in Optical Networks with Larger Demands (2002)
In the problem of Online Call Admission in Optical Networks, briefly called Oca, we are given a graph G = (V, E) together with a set of wavelengths W and a finite sequence # = r1 , r2 , . . . of...
Average Case Analysis of a Hard Dial-a-Ride Problem (2002)
Amin Coja-oghlan, Sven O. Krumke, Till Nierhoff
In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find a shortest transportation for...
Dynamic Routing Algorithms In (2002)
Ralf H Ulsermann, Monika J Ager, Sven O. Krumke, Diana Poensgen, J Org Rambau, Andreas Tuchscherer
Today's telecommunication networks are configured statically. Whenever a connection is established, the customer has permanent access to it. However, it is observed that usually the connection is not...
Real-Time Dispatching Of Guided And Unguided (2002)
Sven O. Krumke, Jrg Rambau, M. Torres
We investigate a real-world large scale vehicle dispatching problem with strict real-time requirements, posed by our cooperation partner, the German Automobile Association. We present computational...
News from the Online Traveling Repairman (2002)
Sven O. Krumke, Diana Poensgen, Leen Stougie
In the traveling repairman problem (TRP), a tour must be found through every one of a set of points (cities) in some metric space such that the weighted sum of completion times of the cities is...
Online Optimization: Competitive Analysis and Beyond (2002)
Contents 0 Introduction 1 1 Preliminaries 9 1.1 What is an Online Problem? . . . . . . . . . . . . . . . . . . . . 9 1.2 Competitive Analysis . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3...
Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows (2001)
Sven Krumke, Rambau Torres, Sven O. Krumke, Jrg Rambau, M. Torres
. Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem VDP is the task to find an assignment...
J Org Rambau, Dietrich Hauptmeier, Sven O. Krumke
In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride...
Budget Constrained Minimum Cost (2001)
Goran Konjevod, Sven O. Krumke
Several practical instances of network design and location theory problems require the network to satisfy multiple constraints. In this paper, we study a graph-theoretic problem that aims to...
News from the Online Traveling Repairman (2001)
Sven O. Krumke, Diana Poensgen, Leen Stougie
In the traveling repairman problem (Trp), a tour must be found through every one of a set of points (cities) in some metric space such that the weighted sum of completion times of the cities is...
How to Cut a Cake Almost Fairly (2001)
Sven O. Krumke, Maarten Lipman, Diana Poensgen, Leen Stougie, Gerhard J. Woeginger
In the cake cutting problem, n 2 players want to cut a cake into n pieces so that every player gets a fair" share of the cake by his own measure. We describe a protocol with n 1 cuts in which each...
Sven O. Krumke, Madhav V. Marathe, S. S. Ravi
this paper, we consider the channel assignment problem for transmitters. The transmission of a station T is intended for and must be received collision-free by all the neighbors of T (i.e., the...
We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly environment. The bin coloring problem is to pack unit size colored items into bins, such...
The Online TSP Against Fair Adversaries (2001)
Michiel Blom, Sven O. Krumke, Leen Stougie, St. Paulusstraat, Leidschendam The Netherlands
this paper we consider the following online variant of the traveling salesman problem (called the Oltsp in the sequel) which was introduced in Ausiello et al. (2000). Cities (requests) arrive online...
Combinatorial Online Optimization in Real Time (2001)
Martin Otschel Krumke, J Rambau, Martin Gr Otschel, Sven O. Krumke, J Org Rambau, Thomas Winter, ...
. Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when...
Online Optimization of Complex Transportation Systems (2001)
Martin Otschel Krumke, J Rambau, Martin Gr Otschel, Sven O. Krumke
. This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company...
Sven Krumke, Willem De, Paepe Rambau Stougie, Sven O. Krumke, J Org Rambau
. We introduce a new problem that was motivated by a (more complicated)
On The Minimum Label Spanning Tree Problem (2000)
Sven O. Krumke, Hans-christoph Wirth
. We study the Minimum Label Spanning Tree Problem. In this problem, we are given an undirected graph whose edges are labeled with colors. The goal is to nd a spanning tree which uses as least...
Approximation Algorithms for Certain Network Improvement Problems (2000)
Sven O. Krumke, R. Ravi, S. S. Ravi
. We study budget constrained network upgrading problems. Such problems aim at nding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an...
Approximation Algorithms for Channel Assignment in Radio Networks (2000)
Sven O. Krumke, Madhav V. Marathe, S. S. Ravi
We consider the channel assignment (broadcast scheduling) problem for packet radio networks. Such networks are naturally modeled by graphs with certain geometric structure. The channel assignment...
Modifying Edges of a Network to Obtain Short Subgraphs (2000)
Kay U. Drangmeister, Sven O. Krumke, Madhav V. Marathe, Hartmut Noltemeier, S. S. Ravi
This paper considers problems of the following type: We are given an edge weighted graph G = (V; E). It is assumed that each edge e of the given network has an associated function c e that species...
The Online Dial-a-Ride Problem under Reasonable Load (2000)
Dietrich Hauptmeier, Sven O. Krumke
. In this paper, we analyze algorithms for the online dial-aride problem with request sets that fulll a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride...
Online Dial-a-Ride Problems: Minimizing the Completion Time (1999)
Norbert Ascheuer, Sven O. Krumke
. We consider the following online dial-a-ride problem (OlDarp): Objects are to be transported between points in a metric space. Transportation requests arrive online, specifying the objects to be...
The Online-TSP Against Fair Adversaries (1999)
Michiel Blom, Sven O. Krumke, Willem De Paepe
. In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and...
The Online Transportation Problem: Competitive Scheduling of Elevators (1999)
Krumke Rambau, Norbert Ascheuer, Sven O. Krumke
. In this paper we consider the following online transportation problem (OLTP): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying...
Approximation Algorithms for Certain Network Improvement Problems (1998)
Sven O. Krumke, R. Ravi, S. S. Ravi
We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an...
m. We denote by q := inffq(x) : x 2 Sg the optimal function value and by S := fx 2 S : q(x) = q g the set of optimal solutions for (QP). Throughout the paper we will make the following assumption:...
Bicriteria Compact Location Problems (1998)
Sven O. Krumke, H. Noltemeier, S. S. Ravi, Madhav V. Marathe
We investigate the complexity and approximability of some location problems when two distance values are specified for each pair of potential sites. These problems involve the selection of a...
Bicriteria Compact Location Problems (1998)
Sven O. Krumke, H. Noltemeier, S. S. Ravi, Madhav V. Marathe
We investigate the complexity and approximability of some location problems when two distance values are specified for each pair of potential sites. These problems involve the selection of a...
m. We denote by q := inffq(x) : x 2 Sg the optimal function value and by S := fx 2 S : q(x) = q g the set of optimal solutions for (QP). Throughout the paper we will make the following assumption:...
Simulation Studies for the Online Dial-a-Ride Problem (1970)
Martin Otschel, Krumke Rambau, Martin Gr Otschel, Dietrich Hauptmeier, Sven O. Krumke
. In a large distribution center of Herlitz AG, Berlin, we investigated the elevator subsystem of the fully automated pallet transportation system. Each elevator may carry one pallet and has to serve...
The Online Transportation Problem: Competitive Scheduling of Elevators (1970)
Norbert Ascheuer, Sven O. Krumke
. In this paper we consider the following online transportation problem (OLTP): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying...
Approximation Algorithms for Certain Network Improvement Problems (1970)
Sven O. Krumke, R. Ravi, S. S. Ravi
. We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given...
The Online Dial-a-Ride Problem under Reasonable Load (1970)
Dietrich Hauptmeier, Sven O. Krumke
. In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online...
An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem (1970)
. In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part...
Budget Constrained Minimum Cost Connected Medians (1970)
Krumke Madhav Marathe, Goran Konjevod, Sven O. Krumke
Several practical instances of network design problems require the network to satisfy multiple constraints. In this paper, we address the Budget Constrained Connected Median Problem: We are given an...
News from the Online Traveling Repairman (1970)
. The traveling repairman problem (TRP) is a variant of the famous traveling salesman problem (TSP). The objective for the TRP is to minimize the latency, that is, the the weighted sum of completion...