KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 10 Dec 2014 14:11:41 +0100Wed, 10 Dec 2014 14:11:41 +0100Transit Dependent Evacuation Planning for Kathmandu Valley: A Case Study
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3944
Due to the increasing number of natural or man-made disasters, the application of operations research methods in evacuation planning has seen a rising interest in the research community. From the beginning, evacuation planning has been highly focused on car-based evacuation. Recently, also the evacuation of transit depended evacuees with the help of buses has been considered.
In this case study, we apply two such models and solution algorithms to evacuate a core part of the metropolitan capital city Kathmandu of Nepal as a hypothetical endangered region, where a large part of population is transit dependent. We discuss the computational results for evacuation time under a broad range of possible scenarios, and derive planning suggestions for practitioners.Urmila Pyakurel; Marc Goerigk; Tanka Dhamala; Horst W. Hamacherreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3944Wed, 10 Dec 2014 14:11:41 +0100An online approach to detecting changes in nonlinear autoregressive models
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2772
In this paper we develop monitoring schemes for detecting structural changes
in nonlinear autoregressive models. We approximate the regression function by a
single layer feedforward neural network. We show that CUSUM-type tests based
on cumulative sums of estimated residuals, that have been intensively studied
for linear regression in both an offline as well as online setting, can be extended
to this model. The proposed monitoring schemes reject (asymptotically) the null
hypothesis only with a given probability but will detect a large class of alternatives
with probability one. In order to construct these sequential size tests the limit
distribution under the null hypothesis is obtained.Claudia Kirch; Joseph Tadjuidje Kamgaingreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2772Mon, 24 Oct 2011 10:46:14 +0000The Multi Terminal q-FlowLoc Problem: A Heuristic
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2290
In this paper the multi terminal q-FlowLoc problem (q-MT-FlowLoc) is introduced. FlowLoc problems combine two well-known modeling tools: (dynamic) network flows and locational analysis. Since the q-MT-FlowLoc problem is NP-hard we give a mixed integer programming formulation and propose a heuristic which obtains a feasible solution by calculating a maximum flow in a special graph H. If this flow is also a minimum cost flow, various versions of the heuristic can be obtained by the use of different cost functions. The quality of this solutions is compared.Stephanie Heller; Horst W. Hamacherreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2290Wed, 02 Mar 2011 16:46:24 +0100Reliable and Restricted Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288
In a dynamic network, the quickest path problem asks for a path minimizing the time needed to send a given amount of flow from source to sink along this path. In practical settings, for example in evacuation or transportation planning, the reliability of network arcs depends on the specific scenario of interest. In this circumstance, the question of finding a quickest path among all those having at least a desired path reliability arises. In this article, this reliable quickest path problem is solved by transforming it to the restricted quickest path problem. In the latter, each arc is associated a nonnegative cost value and the goal is to find a quickest path among those not exceeding a predefined budget with respect to the overall (additive) cost value. For both, the restricted and reliable quickest path problem, pseudopolynomial exact algorithms and fully polynomial-time approximation schemes are proposed.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288Wed, 02 Mar 2011 16:45:38 +0100Efficient Computation of Equilibria in Bottleneck Games via Game Transformation
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2283
Thomas L. Werth; Heike Sperber; Sven O. Krumkereporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2283Thu, 10 Feb 2011 10:37:35 +0100Train Marshalling Problem - Algorithms and Bounds -
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2263
The Train Marshalling Problem consists of rearranging an incoming train in a marshalling yard in such a way that cars with the same destinations appear consecutively in the final train and the number of needed sorting tracks is minimized. Besides an initial roll-in operation, just one pull-out operation is allowed. This problem was introduced by Dahlhaus et al. who also showed that the problem is NP-complete. In this paper, we provide a new lower bound on the optimal objective value by partitioning an appropriate interval graph. Furthermore, we consider the corresponding online problem, for which we provide upper and lower bounds on the competitiveness and a corresponding optimal deterministic online algorithm. We provide an experimental evaluation of our lower bound and algorithm which shows the practical tightness of the results.Katharina Beygang; Sven O. Krumke; Florian Dahmsreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2263Mon, 10 Jan 2011 10:26:59 +0100Min-Max Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249
In a dynamic network, the quickest path problem asks for a path such that a given amount of flow can be sent from source to sink via this path in minimal time. In practical settings, for example in evacuation or transportation planning, the problem parameters might not be known exactly a-priori. It is therefore of interest to consider robust versions of these problems in which travel times and/or capacities of arcs depend on a certain scenario. In this article, min-max versions of robust quickest path problems are investigated and, depending on their complexity status, exact algorithms or fully polynomial-time approximation schemes are proposed.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249Fri, 19 Nov 2010 09:57:06 +0100Dynamic Multi-Period Routing With Two Classes
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2228
In the Dynamic Multi-Period Routing Problem, one is given a new set of requests at the beginning of each time period. The aim is to assign requests to dates such that all requests are fulfilled by their deadline and such that the total cost for fulling the requests is minimized. We consider a generalization of the problem which allows two classes of requests: The 1st class requests can only be fulfilled by the 1st class server, whereas the 2nd class requests can be fulfilled by either the 1st or 2nd class server. For each tour, the 1st class server incurs a cost that is alpha times the cost of the 2nd class server, and in each period, only one server can be used. At the beginning of each period, the new requests need to be assigned to service dates. The aim is to make these assignments such that the sum of the costs for all tours over the planning horizon is minimized. We study the problem with requests located on the nonnegative real line and prove that there cannot be a deterministic online algorithm with a competitive ratio better than alpha. However, if we require the difference between release and deadline date to be equal for all requests, we can show that there is a min{2*alpha, 2 + 2/alpha}-competitive algorithm.Sven O. Krumke; Christiane Zeckreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2228Mon, 16 Aug 2010 15:41:41 +0200Online Delay Management
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2197
We present extensions to the Online Delay Management Problem on a Single Train Line. While a train travels along the line, it learns at each station how many of the passengers wanting to board the train have a delay of delta. If the train does not wait for them, they get delayed even more since they have to wait for the next train. Otherwise, the train waits and those passengers who were on time are delayed by delta. The problem consists in deciding when to wait in order to minimize the total delay of all passengers on the train line. We provide an improved lower bound on the competitive ratio of any deterministic online algorithm solving the problem using game tree evaluation. For the extension of the original model to two possible passenger delays delta_1 and delta_2, we present a 3-competitive deterministic online algorithm. Moreover, we study an objective function modeling the refund system of the German national railway company, which pays passengers with a delay of at least Delta a part of their ticket price back. In this setting, the aim is to maximize the profit. We show that there cannot be a deterministic competitive online algorithm for this problem and present a 2-competitive randomized algorithm.Sven O. Krumke; Clemens Thielen; Christiane Zeckreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2197Thu, 08 Jul 2010 08:52:34 +0200Generalized Max Flow in Series-Parallel Graphs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2179
In the generalized max flow problem, the aim is to find a maximum flow in a generalized network, i.e., a network with multipliers on the arcs that specify which portion of the flow entering an arc at its tail node reaches its head node. We consider this problem for the class of series-parallel graphs. First, we study the continuous case of the problem and prove that it can be solved using a greedy approach. Based on this result, we present a combinatorial algorithm that runs in O(m*m) time and a dynamic programming algorithm with running time O(m*log(m)) that only computes the maximum flow value but not the flow itself. For the integral version of the problem, which is known to be NP-complete, we present a pseudo-polynomial algorithm.Katharina Beygang; Sven O. Krumke; Christiane Zeckreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2179Tue, 09 Mar 2010 07:57:55 +0100Selfish Bin Coloring
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2145
We introduce a new game, the so-called bin coloring game, in which selfish players control colored items and each player aims at packing its item into a bin with as few different colors as possible. We establish the existence of Nash and strong as well as weakly and strictly Pareto optimal equilibria in these games in the cases of capacitated and uncapacitated bins. For both kinds of games we determine the prices of anarchy and stability concerning those four equilibrium concepts. Furthermore, we show that extreme Nash equilibria, those with minimal or maximal number of colors in a bin, can be found in time polynomial in the number of items for the uncapcitated case.Leah Epstein; Sven O. Krumke; Asaf Levin; Heike Sperberreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2145Fri, 16 Oct 2009 08:55:08 +0200Earliest Arrival Flows in Series-Parallel Graphs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2137
We present an exact algorithm for computing an earliest arrival flow in a discrete time setting on series-parallel graphs. In contrast to previous results for the earliest arrival flow problem this algorithm runs in polynomial time.Stefan Ruzika; Heike Sperber; Mechthild Steinerreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2137Tue, 06 Oct 2009 15:31:20 +0200Truthful Mechanisms for Selfish Routing and Two-Parameter Agents
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2055
We prove a general monotonicity result about Nash flows in directed networks and use it for the design of truthful mechanisms in the setting where each edge of the network is controlled by a different selfish agent, who incurs costs when her edge is used. The costs for each edge are assumed to be linear in the load on the edge. To compensate for these costs, the agents impose tolls for the usage of edges. When nonatomic selfish network users choose their paths through the network independently and each user tries to minimize a weighted sum of her latency and the toll she has to pay to the edges, a Nash flow is obtained. Our monotonicity result implies that the load on an edge in this setting can not increase when the toll on the edge is increased, so the assignment of load to the edges by a Nash flow yields a monotone algorithm. By a well-known result, the monotonicity of the algorithm then allows us to design truthful mechanisms based on the load assignment by Nash flows. Moreover, we consider a mechanism design setting with two-parameter agents, which is a generalization of the case of one-parameter agents considered in a seminal paper of Archer and Tardos. While the private data of an agent in the one-parameter case consists of a single nonnegative real number specifying the agent's cost per unit of load assigned to her, the private data of a two-parameter agent consists of a pair of nonnegative real numbers, where the first one specifies the cost of the agent per unit load as in the one-parameter case, and the second one specifies a fixed cost, which the agent incurs independently of the load assignment. We give a complete characterization of the set of output functions that can be turned into truthful mechanisms for two-parameter agents. Namely, we prove that an output function for the two-parameter setting can be turned into a truthful mechanism if and only if the load assigned to every agent is nonincreasing in the agent's bid for her per unit cost and, for almost all fixed bids for the agent's per unit cost, the load assigned to her is independent of the agent's bid for her fixed cost. When the load assigned to an agent is continuous in the agent's bid for her per unit cost, it must be completely independent of the agent's bid for her fixed cost. These results motivate our choice of linear cost functions without fixed costs for the edges in the selfish routing setting, but the results also seem to be interesting in the context of algorithmic mechanism design themselves.Clemens Thielenreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2055Thu, 15 Jan 2009 15:21:50 +0100Minimum Cut Tree Games
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2049
In this paper we introduce a cooperative game based on the minimum cut tree problem which is also known as multi-terminal maximum flow problem. Minimum cut tree games are shown to be totally balanced and a solution in their core can be obtained in polynomial time. This special core allocation is closely related to the solution of the original graph theoretical problem. We give an example showing that the game is not supermodular in general, however, it is for special cases and for some of those we give an explicit formula for the calculation of the Shapley value.Anne M. Schwahnreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2049Fri, 19 Dec 2008 12:48:05 +0100How to find Nash equilibria with extreme total latency in network congestion games?
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2034
We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it depends on the graph topology and the number of users. In our context best and worst equilibria are those with minimum respectively maximum total latency. We establish that both problems can be solved by a Greedy algorithm with a suitable tie breaking rule on parallel links. On series-parallel graphs finding a worst Nash equilibrium is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. Additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph.Heike Sperberreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2034Wed, 29 Oct 2008 15:50:44 +0100Locating stops along bus or railway lines - a bicriterial problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1371
In this paper we consider the location of stops along the edges of an already existing public transportation network, as introduced in [SHLW02]. This can be the introduction of bus stops along some given bus routes, or of railway stations along the tracks in a railway network. The goal is to achieve a maximal covering of given demand points with a minimal number of stops. This bicriterial problem is in general NP-hard. We present a nite dominating set yielding an IP-formulation as a bicriterial set covering problem. We use this formulation to observe that along one single straight line the bicriterial stop location problem can be solved in polynomial time and present an e cient solution approach for this case. It can be used as the basis of an algorithm tackling real-world instances.Anita SchÃ¶belreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1371Thu, 23 Jan 2003 10:59:07 +0100