The online target date assignment problem (2005)
Krumke, S.O., Megow, N., Rambau, J., Tuchscherer, A., Vredeveld, T.
Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the...
How to cut a cake almost fairly (2002)
Krumke, S.O., Lipmann, M., Paepe, W. De, Poensgen, D., Rambau, J., Stougie, L., ...
Euler is Standing in Line (2001)
D. Hauptmeier, S. O. Krumke, J. Rambau, H. -c. Wirth
In this paper we study algorithms for Dial-a-Ride" transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to nd...
Multiscale Concepts for Moving Horizon Optimization (2001)
T. Binder, L. Blank, W. Dahmen, W. Marquardt, M. Grotschel, S. O. Krumke, ...
In chemical engineering complex dynamic optimization problems formulated on moving horizons have to be solved on-line. In this work, we present a multiscale approach based on wavelets where a...
Euler is Standing in Line - Dial-a-Ride Problems with Precedence-Constraints (2000)
D. Hauptmeier, S. O. Krumke, J. Rambau, H. -c. Wirth
In this paper we study algorithms for Dial-a-Ride" transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to nd...
Flow Improvement and Network Flows with Fixed Costs (2000)
S. O. Krumke, Konrad-zuse-zentrum Fur Informationstechnik Berlin, H. Noltemeier, S. Schwarz, H. -c. Wirth
this paper are NP-hard to solve. We present various approximation algorithms for the problems under study.
Improving Minimum Cost Spanning Trees by Upgrading Nodes (1999)
S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, ...
We study budget constrained network upgrading problems. We are given an undirected edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the weight...
Modifying Edges of a Network to Obtain Short Subgroups (1998)
K. U. Drangmeister, S. O. Krumke, M. V. Marathe, H. 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 speci#es the...
Improving Spanning Trees by Upgrading Nodes (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeir, R. Ravi, S. Ravi
Id: upgrade.tex,v 2.2 1997#09#18 13:14:08 krumke Exp wirth We study bottleneck constrained network upgrading problems.We are given an edge weighted graph G =#V;E# where node v 2 V can be upgraded at...
Upgrading Bottleneck Constrained Forests (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi
. We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the delay of each...
Modifying Networks to Obtain Low Cost Trees (1998)
S. O. Krumke, H. Noltemeier, M. V. Marathe, S. S. Ravi, K. U. Drangmeister
We consider the problem of reducing the edge lengths of a given network so that the modified network has a spanning tree of small total length. It is assumed that each edge e of the given network has...
Complexity and Approximability of Certain Bicriteria Location Problems (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. 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...
Compact Location Problems (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
We consider the problem of placing a specified number (p) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a...
Compact Location Problems with Budget and Communication Constraints (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
. We consider the problem of placing a specified number p of facilities on the nodes of a given network with two nonnegative edge-- weight functions so as to minimize the diameter of the placement...
Compact Location Problems (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
We consider the problem of placing a specified number (p) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a...
Complexity and Approximability of Certain Bicriteria Location Problems (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. 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...
Compact Location Problems with Budget and Communication Constraints (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
. We consider the problem of placing a specified number p of facilities on the nodes of a given network with two nonnegative edge-- weight functions so as to minimize the diameter of the placement...
Modifying Networks to Obtain Low Cost Trees (1998)
S. O. Krumke, H. Noltemeier, M. V. Marathe, S. S. Ravi, K. U. Drangmeister
We consider the problem of reducing the edge lengths of a given network so that the modified network has a spanning tree of small total length. It is assumed that each edge e of the given network has...
Compact Location Problems (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
We consider the problem of placing a specified number (p) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a...
Complexity and Approximability of Certain Bicriteria Location Problems (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. 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...
On a Generalization of the p-Center Problem (1998)
this paper, we study a generalization of p--Center, which we call the ff--
Compact Location Problems with Budget and Communication Constraints (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
. We consider the problem of placing a specified number p of facilities on the nodes of a given network with two nonnegative edge-- weight functions so as to minimize the diameter of the placement...
Euler is Standing in Line - Dial-a-Ride Problems with FIFO-Precedence-Constraints (1970)
Dietrich Hauptmeier, Krumke Rambau, Hans-christoph Wirth, D. Hauptmeier, S. O. Krumke, J. Rambau
. In this paper we study algorithms for "Dial-a-Ride" transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to...
Compact Location Problems (1970)
S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
We consider the problem of placing a specified number (p) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a...
Improving Minimum Cost Spanning Trees by Upgrading Nodes (1970)
S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, ...
We study budget constrained network upgrading problems. We are given an undirected edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the weight...
Upgrading Bottleneck Constrained Forests (1970)
S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi, H. -c. Wirth
. We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the delay of each...
The Online Target Date Assignment Problem
Heinz,S., Krumke,S.O., Megow,N., Rambau,J., Tuchscherer,A., Vredeveld,T.
Many online problems encountered in real-life involve a twostage decision process: upon arrival of a new request, an irrevocable firststage decision (the assignment of a specific resource to the...