We consider the speed scaling problem where the quality of service objective is deadline feasibility and the power objective is temperature. In the case of batched jobs, we give a simple algorithm to compute the optim...
详细信息
ISBN:
(纸本)9783642197536
We consider the speed scaling problem where the quality of service objective is deadline feasibility and the power objective is temperature. In the case of batched jobs, we give a simple algorithm to compute the optimal schedule. For general instances, we give a new online algorithm, and obtain an upper bound on the competitive ratio of this algorithm that is an order of magnitude better than the best previously known bound upper bound on the competitive ratio for this problem.
The L(2,1)-labeling problem consists of assigning colors from the integer set 0, ... , lambda to the nodes of a graph G in such a way that nodes at a distance of at most two get different colors, while adjacent nodes ...
详细信息
ISBN:
(纸本)9783642197536
The L(2,1)-labeling problem consists of assigning colors from the integer set 0, ... , lambda to the nodes of a graph G in such a way that nodes at a distance of at most two get different colors, while adjacent nodes get colors which are at least two apart. The aim of this problem is to minimize A and it is in general NP-complete. In this paper the problem of L(2, 1)-labeling unigraphs, i.e. graphs uniquely determined by their own degree sequence up to isomorphism, is addressed and a 3/2-approximate algorithm for L(2, 1)-labeling unigraphs is designed. This algorithm runs in O(n) time, improving the time of the algorithm based on the greedy technique, requiring O(m) time, that may be near to Theta(n(2)) for unigraphs.
The proceedings contain 24 papers. The topics discussed include: distributed decision problems: the locality angle;managing power heterogeneity;the mathematics of mobility;speed scaling to manage temperature;alternati...
ISBN:
(纸本)9783642197536
The proceedings contain 24 papers. The topics discussed include: distributed decision problems: the locality angle;managing power heterogeneity;the mathematics of mobility;speed scaling to manage temperature;alternative route graphs in road networks;robust line planning in case of multiple pools and disruptions;exact algorithms for intervalizing colored graphs;energy-efficient due date scheduling;go with the flow: the direction-based fŕechet distance of polygonal curves;a comparison of three algorithms for approximating the distance distribution in real-world graphs;exploiting bounded signal flow for graph orientation based on cause-effect pairs;on greedy and submodular matrices;a scenario-based approach for robust linear optimization;conflict propagation and component recursion for canonical labeling;improved taxation rate for bin packing games;and multi-channel assignment for communication in radio networks.
Despite disillusioning worst-case behavior, classic algorithms for single-source shortest-paths (SSSP) like Bellman-Ford are still being used in practice, especially due to their simple data structures. However, surpr...
详细信息
ISBN:
(纸本)9783642197536
Despite disillusioning worst-case behavior, classic algorithms for single-source shortest-paths (SSSP) like Bellman-Ford are still being used in practice, especially due to their simple data structures. However, surprisingly little is known about the average-case complexity of these approaches. We provide new theoretical and experimental results for the performance of classic label-correcting SSSP algorithms on graph classes with non-negative random edge weights. In particular, we prove a tight lower bound of Omega(n(2)) for the running times of Bellman-Ford on a class of sparse graphs with O(n) nodes and edges;the best previous bound was Omega(n(4/3-epsilon)). The same improvements are shown for Pallottino's algorithm. We also lift a lower bound for the approximate bucket implementation of Dijkstra's algorithm from Omega(n log n/log log n) to Omega(n(1.2-epsilon)). Furthermore, we provide an experimental evaluation of our new graph classes in comparison with previously used test inputs.
The proceedings contain 24 papers. The special focus in this conference is on Smart grids, Active houses, Smart meters, Intelligent applications, Communication and control protocols, Multi-agent systems, Power system ...
ISBN:
(纸本)9783642193217
The proceedings contain 24 papers. The special focus in this conference is on Smart grids, Active houses, Smart meters, Intelligent applications, Communication and control protocols, Multi-agent systems, Power system automation, Electric vehicles, Competitive environment and Distributed generation. The topics include: microgrid modelling and analysis using game theory methods;implementation of gossip algorithms in power systems;a review of ICT considerations in actual AMI deployments;performance evaluation of a web service enabled smart metering platform;a review of customer management tools;high level requirements for smart meters that will enable the efficient deployment of electric vehicles;suppressing peak load at simultaneous demand of electric heating in residential areas;design and implementation of a practical smart home system based on DECT technology;field trials towards integrating smart houses with the smart grid;demand side management in smart buildings using KNX/EIB;cutting-edge information and telecommunication technologies meet energy;routing and G-networks to optimise energy and quality of service in packet networks;the beywatch conceptual model for demand-side management;monitoring and control for energy efficiency in the smart house;the powermatching city field test;ICT-platform based distributed control in electricity grids with a large share of distributed energy resources and renewable energy sources and cellular system model for smart grids combining active distribution networks and smart buildings.
We try to show in this paper that animations and simulations are often presented as how learning tools, even though all the animations are not really able to fulfill this role. We define what a graphic animation and s...
详细信息
ISBN:
(纸本)9783642211522
We try to show in this paper that animations and simulations are often presented as how learning tools, even though all the animations are not really able to fulfill this role. We define what a graphic animation and simulation to show that, in education systems, they should only be used if they have something to do with: the material to learn the process of learning and / or characteristics of the learner, thus leaving aside the animations used solely for marketing purposes. We then present and discuss a simple but pedagogically relevant simulation included a help system to learn and practicealgorithms. Finally, we propose a guideline establishing general relationships between types of learning activities, types of knowledge implemented and the types of animations and simulations.
The proposed work focuses on Genetic-Fuzzy approach to identify student's skills. It is an integrated approach of education and technology implementing theory of Multiple Intelligence. The objective is to reduce t...
详细信息
ISBN:
(纸本)9783642178801
The proposed work focuses on Genetic-Fuzzy approach to identify student's skills. It is an integrated approach of education and technology implementing theory of Multiple Intelligence. The objective is to reduce the system's developmental and maintenance effort and automatically evolve strong rules. The proposed model is a novel evolutionary hybrid approach to measure and classify multiple intelligence in a friendly way. The paper includes general architecture of the model with front end and back end designs including encoding strategy, fitness function, crossover operator, and sample evolved rules and results. It concludes with the scope and application of the work to other domains.
Ubiquitous computing environments are complex systems since they support a variety of different input modalities such as voice, touch and keyboard/mouse input. Especially inexperienced users (e.g., elderly or novel) m...
详细信息
ISBN:
(纸本)9783642216756
Ubiquitous computing environments are complex systems since they support a variety of different input modalities such as voice, touch and keyboard/mouse input. Especially inexperienced users (e.g., elderly or novel) might be confused with the abundance of interaction opportunities. This paper presents an approach to specify smart user assistance for mobile devices. The mobile application shows performable tasks, explains modalities and commands, and provides interactive exercises in order to get the user familiar with the system interaction. The complexity of the interactive exercises and the selection of most suitable modalities are adapted based on user characteristics. The advantage is that users become acquainted with the use of different modalities step by step.
Data saturation of satellite navigation systems (already a problem with location based services) will become particularly acute in the emerging area of networked electric vehicles (NEV). Sophisticated energy managemen...
详细信息
ISBN:
(纸本)9783642217081;9783642217074
Data saturation of satellite navigation systems (already a problem with location based services) will become particularly acute in the emerging area of networked electric vehicles (NEV). Sophisticated energy management and navigation software may solve a technology integration challenge, but it will leave unresolved the usability implications for drivers and fleet operators. These include navigation data specific to commercial electric vehicles;delivery scheduling, routes, times, traffic congestion avoidance, range & charge levels etc. Many are time dependent factors that complicate interaction with a map based navigation system. They also risk augmenting driver stress and distraction induced errors. This Paper has two objectives. Firstly we examine the problem of information saturation of navigation systems. Secondly we undertook a series of user tests to evaluate an alternative NEV navigation system. The DHS solution is a compressed data feed delivering "just in time" multimodal prompts embedded in the map route. The test results demonstrated improved driver comprehension and reduced driver glance away time from road to navigation system.
暂无评论