CiteSeerX Scientific Literature Digital Library and Search Engine
CiteSeerX is a scientific literature digital library and search engine that focuses primarily on the literature in computer and information science. CiteSeerx aims to improve the dissemination of scientific literature and to provide improvements in functionality, usability, availability, cost, comprehensiveness, efficiency, and timeliness in the access of scientific and scholarly knowledge
Mostrando recursos 1 - 20 de 4,143,581
TIME-DEPENDENT STOCHASTIC SHORTEST PATH(S) ALGORITHMS FOR A SCHEDULED TRANSPORTATION NETWORK - Qiujin Wu; Joanna Hartley; David Al-dabass
Following on from our work concerning travellers’ preferences in public transportation networks (Wu and Hartley, 2004), we introduce the concept of stochasticity to our algorithms. Stochasticity greatly increases the complexity of the route finding problem, so greater algorithmic efficiency becomes imperative. Public transportation networks (buses, trains) have two important features: edges can only be traversed at certain points in time and the weights of these edges change in a day and have an uncertainty associated with them. These features determine that a public transportation network is a stochastic and time-dependent network. Finding multiple shortest paths in a both stochastic and...
Point-to-Point Shortest Path Algorithms with Preprocessing - Andrew V. Goldberg
This is a survey of some recent results on point-to-point shortest path algorithms. This classical optimization problem received a lot of attention lately and significant progress has been made. After an overview of classical results, we study recent heuristics that solve the problem while examining only a small portion of the input graph; the graph can be very big. Note that the algorithms we discuss find exact shortest paths. These algorithms are heuristic because they perform well only on some graph classes. While their performance has been good in experimental studies, no theoretical bounds are known to support the experimental...
Hub Label Compression - Daniel Delling; Andrew V. Goldberg; Renato F. Werneck
The hub labels (HL) algorithm is the fastest known technique for computing driving times on road networks, but its practical appli-cability can be limited by high space requirements relative to the best competing methods. We develop compression techniques that substantially reduce HL space requirements with a small performance penalty.
Customizable Point-of-Interest Queries in Road Networks - Daniel Delling; Renato F. Werneck
We present a unified framework for dealing with exact point-of-interest (POI) queries in dynamic continental road networks within interactive applications. We show that partition-based algorithms developed for point-to-point shortest path computations can be naturally extended to handle augmented queries such as finding the closest restaurant or the best post office to stop on the way home, always ranking POIs according to a user-defined cost function. Our solution allows different trade-offs between indexing effort (time and space) and query time. Our most flexible variant allows the road network to change frequently (to account for traffic information or personalized cost functions) and...
PHAST: hardware-accelerated shortest path trees - Daniel Delling; Andrew V. Goldberg; Andreas Nowatzyk; Renato F. Werneck
We present a novel algorithm to solve the nonnegative single-source shortest path problem on road networks and graphs with low highway dimension. After a quick preprocessing phase, we can compute all distances from a given source in the graph with essentially a linear sweep over all vertices. Because this sweep is independent of the source, we are able to reorder vertices in advance to exploit locality. Moreover, our algorithm takes advantage of features of modern CPU architectures, such as SSE and multiple cores. Compared to Dijkstra’s algorithm, our method needs fewer operations, has better locality, and is better able to...
Limited Participation in International Business Cycle Models: A Formal Evaluation - Xiaodan Gao; Viktoria Hnatkovska; Vadim Marmer
In this paper, we argue that limited asset market participation (LAMP) plays an important role in explaining international business cycles. We show that when LAMP is introduced into an otherwise standard model of international business cycles, the performance of the model improves significantly, especially in matching cross-country correlations. To perform formal evaluation of the models we develop a novel statistical procedure that adapts the statistical framework of Vuong (1989) to DSGE models. Using this methodology, we show that the improvements brought out by LAMP are statistically significant, leading a model with LAMP to outperform a representative agent model. Furthermore, when...
A quasi-static boundary value problem in multi-surface elastoplasticity: Part 2 . . . - Martin Brokate; Carsten Carstensen; Jan Valdman
Multi-yield elastoplasticity models a material with more than one plastic state and hence allows for refined approximation of irreversible deformations. Aspects of the mathematical modeling and a proof of unique existence of weak solutions can be found in part I of this paper [BCV04]. In this part II we establish a canonical time-space discretization of the evolution problem and present various algorithms for the solving really discrete problems. Based on a global Newton-Raphson solver, we carefully study and solve elementwise inner iterations. Numerical examples illustrate the model and its flexibility to allow for refined hysteresis curves.
ON OPTIMAL CONTROL OF A SWEEPING PROCESS COUPLED WITH AN ORDINARY DIFFERENTIAL EQUATION - Lukas Adam, et al.
We study a special case of an optimal control problem governed by a differential equation and a differential rate–independent variational inequality, both with given initial conditions. Under certain conditions, the variational inequality can be reformulated as a differential inclusion with discontinuous right-hand side. This inclusion is known as sweeping process. We perform a discretization scheme and prove the convergence of optimal solutions of the discretized problems to the optimal solution of the original problem. For the discretized problems we study the properties of the solution map and compute its coderivative. Employing an appropriate chain rule, this enables us to compute...
A quasi-static boundary value problem in multi-surface elastoplasticity: Part 1 -- Analysis - Martin Brokate; Carsten Carstensen; Jan Valdman
The quasi-static evolution of an elastoplastic body with a multi-surface constitutive law of linear kinematic hardening type allows the modeling of curved stress-strain relations. It generalizes classical small-strain elastoplasticity from one to various plastic phases. This paper presents the mathematical models and proves existence and uniqueness of the solution of the corresponding initial-boundary value problem. The analysis involves an explicit estimate for the effective ellipticity constant.
Toeplitz Operators on Symplectic Manifolds - Xiaonan Ma; George Marinescu
We study the Berezin-Toeplitz quantization on symplectic manifolds mak-ing use of the full off-diagonal asymptotic expansion of the Bergman kernel. We give also a characterization of Toeplitz operators in terms of their asymptotic expansion. The semi-classical limit properties of the Berezin-Toeplitz quantization for non-compact manifolds and orbifolds are also established.
Investigation of advanced strain-path dependent material models for sheet metal forming simulations - Badis Haddag; Tudor Balan; Farid Abed-meraim
Sheet metal forming processes often involve complex loading sequences. To improve the prediction of some undesirable phenomena, such as springback, physical behavior models should be considered. This paper investigates springback behavior predicted by advanced elastoplastic hardening models which combine isotropic and kinematic hardening and take strain-path changes into account. A dislocation-based microstructural hardening model formulated from physical observations and the more classical cyclic model of Chaboche have been considered in this work. Numerical implementation was carried out in the ABAQUS software using a return mapping algorithm with a combined backward Euler and semi-analytical integration scheme of the constitutive equations. The...
Wellposedness of kinematic hardening models in . . . - Martin Brokate; Pavel Krejčí
We consider a certain type of rate independent elastoplastic constitutive laws for nonlinear kinematic hardening which include the models of Frederick-Armstrong, Bower and Mróz. We prove results concerning existence, uniqueness and continuous dependence for the stress-strain evolution considered as a function of time (but not of space). As an auxiliary result, we also prove a theorem concerning the Lipschitz continuity of the vector play operator.
Clamped elastic-ideally plastic beams and Prandtl-Ishlinskii hysteresis operators - Jürgen Sprekels; Pavel Krejčí
We consider a model for one-dimensional transversal oscillations of an elastic-ideally plastic beam. It is based on the von Mises model of plasticity and leads after a dimensional reduction to a fourth-order partial differential equation with a hysteresis operator of Prandtl-Ishlinskii type whose weight function is given explicitly. In this paper, we study the case of clamped beams involving a kinematic hardening in the stress-strain relation. As main result, we prove the existence and uniqueness of a weak solution. The method of proof, based on spatially semidiscrete approximations, strongly relies on energy dissipation properties of one-dimensional hysteresis operators.
Engineering Route Planning Algorithms - Daniel Delling; Peter Sanders; Dominik Schultes; Dorothea Wagner
Algorithms for route planning in transportation networks have recently undergone a rapid development, leading to methods that are up to three million times faster than Dijkstra’s algorithm. We give an overview of the techniques enabling this development and point out frontiers of ongoing research on more challenging variants of the problem that include dynamically changing networks, time-dependent routing, and flexible objective functions.
International Trade in Durable Goods: Understanding Volatility, Cyclicality, and Elasticities - Charles Engel; Jian Wang
Data for OECD countries document: 1. imports and exports are about three times as volatile as GDP; 2. imports and exports are pro-cyclical, and positively correlated with each other; 3. net exports are counter-cyclical. Standard models fail to replicate the behavior of imports and exports, though they can match net exports relatively well. Inspired by the fact that a large fraction of international trade is in durable goods, we propose a two-country two-sector model, in which durable goods are traded across countries. Our model can match the business cycle statistics on the volatility and comovement of the imports and exports...
ON SOLVING DYNAMIC SHORTEST PATH PROBLEMS - Ebrahim Nasrabadi; S. Mehdi Hashemi
Given a dynamic network with n nodes and m arcs in which all attributes including travel times, travel costs and waiting costs may change dynamically over a time horizon T. The dynamic shortest path problem is to determine a path from a specified source node to every other node with minimal total cost, subject to the constraint that the total traverse time is at most T. This problem can be formulated in two ways depending on whether a discrete or continuous representation of time is used. In this paper, we present an O(nT(n+T)) time algorithm for solving the discrete-time version...