@misc{HarksHeinzPfetsch, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc}, title = {Competitive Online Multicommodity Routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9212}, number = {06-27}, abstract = {We study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining the routing weights. We discuss an online algorithm that routes each commodity by minimizing a convex cost function that depends on the demands that are previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is \$4K/2+K\$-competitive, where \$K\$ is the number of commodities. For the parallel arc case this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.}, language = {en} } @misc{HarksHeinzPfetsch, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc}, title = {Competitive Online Multicommodity Routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9599}, number = {07-16}, abstract = {In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.}, language = {en} } @misc{HeinzKrumkeMegowetal., author = {Heinz, Stefan and Krumke, Sven and Megow, Nicole and Rambau, J{\"o}rg and Tuchscherer, Andreas and Vredeveld, Tjark}, title = {The Online Target Date Assignment Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8945}, number = {05-61}, abstract = {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 request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an \emph{Online Target Date Assignment Problem} (\textsc{OnlineTDAP}) as a general framework for online problems with this nature. Requests for the \textsc{OnlineTDAP} become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.\,g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the \emph{downstream cost}, the optimal cost of processing all requests at that date w.\,r.\,t.\ some fixed downstream offline optimization problem (e.\,g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the \textsc{OnlineTDAP} independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the par ticular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.}, language = {en} } @misc{HeinzKaibelPeinhardtetal., author = {Heinz, Stefan and Kaibel, Volker and Peinhardt, Matthias and Rambau, J{\"o}rg and Tuchscherer, Andreas}, title = {LP-Based Local Approximation for Markov Decision Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9131}, number = {06-20}, abstract = {The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.\,g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an \$\varepsilon\$-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies.}, language = {en} }