Abstract: Implementation of a commercial application to a
grid infrastructure introduces new challenges in managing the
quality-of-service (QoS) requirements, most stem from the fact
that negotiation on QoS between the user and the service provider
should strictly be satisfied. An interesting commercial application
with a wide impact on a variety of fields, which can benefit from
the computational grid technologies, is three–dimensional (3-D)
rendering. In order to implement, however, 3-D rendering to a
grid infrastructure, we should develop appropriate scheduling
and resource allocation mechanisms so that the negotiated (QoS)
requirements are met. Efficient scheduling schemes require
modeling and prediction of rendering workload. In this paper
workload prediction is addressed based on a combined fuzzy
classification and neural network model. Initially, appropriate
descriptors are extracted to represent the synthetic world. The
descriptors are obtained by parsing RIB formatted files, which
provides a general structure for describing computer-generated
images. Fuzzy classification is used for organizing rendering
descriptor so that a reliable representation is accomplished which
increases the prediction accuracy. Neural network performs
workload prediction by modeling the nonlinear input-output
relationship between rendering descriptors and the respective
computational complexity. To increase prediction accuracy, a
constructive algorithm is adopted in this paper to train the neural
network so that network weights and size are simultaneously
estimated. Then, a grid scheduler scheme is proposed to estimate
the queuing order that the tasks should be executed and the
most appopriate processor assignment so that the demanded
QoS are satisfied as much as possible. A fair scheduling policy is
considered as the most appropriate. Experimental results on a real
grid infrastructure are presented to illustrate the efficiency of the
proposed workload prediction — scheduling algorithm compared
to other approaches presented in the literature.
Abstract: In this paper we consider the problem of web page usage prediction in a web site by modeling users¢ navigation history and web page content with weighted suffix trees. This user¢s navigation prediction can be exploited either in an on-line recommendation system in a web site or in a web page cache system. The method proposed has the advantage that it demands a constant amount of computational effort per one user¢s action and consumes a relatively small amount of extra memory space. These features make the method ideal for an on-line working environment. Finally, we have performed an evaluation of the proposed scheme with experiments on various web site log files and web pages and we have found that its quality performance is fairly well and in many cases an outperforming one.
Abstract: We consider two approaches that model timetable information in public transportation systems
as shortest-path problems in weighted graphs. In the time-expanded approach, every event at
a station, e.g., the departure of a train, is modeled as a node in the graph, while in the timedependent
approach the graph contains only one node per station. Both approaches have been
recently considered for (a simplified version of) the earliest arrival problem, but little is known
about their relative performance. Thus far, there are only theoretical arguments in favor of the
time-dependent approach. In this paper, we provide the first extensive experimental comparison of
the two approaches. Using several real-world data sets, we evaluate the performance of the basic
models and of several new extensions towards realistic modeling. Furthermore, new insights on
solving bicriteria optimization problems in both models are presented. The time-expanded approach
turns out to be more robust for modeling more complex scenarios, whereas the time-dependent
approach shows a clearly better performance.
Abstract: We consider two approaches that model timetable information in public transportation systems
as shortest-path problems in weighted graphs. In the time-expanded approach, every event at
a station, e.g., the departure of a train, is modeled as a node in the graph, while in the timedependent
approach the graph contains only one node per station. Both approaches have been
recently considered for (a simplified version of) the earliest arrival problem, but little is known
about their relative performance. Thus far, there are only theoretical arguments in favor of the
time-dependent approach. In this paper, we provide the first extensive experimental comparison of
the two approaches. Using several real-world data sets, we evaluate the performance of the basic
models and of several new extensions towards realistic modeling. Furthermore, new insights on
solving bicriteria optimization problems in both models are presented. The time-expanded approach
turns out to be more robust for modeling more complex scenarios, whereas the time-dependent
approach shows a clearly better performance.
Abstract: We present a set of three new time-dependent models with
increasing
exibility for realistic route planning in
flight networks. By
these means, we obtain small graph sizes while modeling airport procedures
in a realistic way. With these graphs, we are able to efficiently
compute a set of best connections with multiple criteria over a full day.
It even turns out that due to the very limited graph sizes it is feasible
to precompute full distance tables between all airports. As a result, best
connections can be retrieved in a few microseconds on real world data.
Abstract: Evolutionary dynamics have been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [15]. Recently, this approach has been generalized in [13] by arranging individuals on the nodes of a network (in general, directed). In this setting, the existence of directed arcs enables the simulation of extreme phenomena, where the fixation probability of a randomly placed mutant (i.e. the probability that the offsprings of the mutant eventually spread over the whole population) is arbitrarily small or large. On the other hand, undirected networks (i.e. undirected graphs) seem to have a smoother behavior, and thus it is more challenging to find suppressors/amplifiers of selection, that is, graphs with smaller/greater fixation probability than the complete graph (i.e. the homogeneous population). In this paper we focus on undirected graphs. We present the first class of undirected graphs which act as suppressors of selection, by achieving a fixation probability that is at most one half of that of the complete graph, as the number of vertices increases. Moreover, we provide some generic upper and lower bounds for the fixation
probability of general undirected graphs. As our main contribution, we introduce the natural alternative of the model proposed in [13]. In our new evolutionary model, all individuals interact simultaneously and the result is a compromise between aggressive and non-aggressive individuals. That is, the behavior of the individuals in our new model and in the model of [13] can be interpreted as an “aggregation” vs. an “all-or-nothing” strategy, respectively. We prove that our new model of mutual influences admits a potential function, which guarantees the convergence of the system for any graph topology and any initial fitness vector of the individuals. Furthermore, we prove fast convergence to the stable state for the case of the complete graph, as well as we provide almost tight bounds on the limit fitness of the individuals. Apart from being important on its own, this new evolutionary model appears to be useful also in the abstract modeling of control mechanisms over invading populations in networks. We demonstrate this by introducing and analyzing two alternative control approaches, for which we bound the time needed to stabilize to the “healthy” state of the system.