+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +**********************************************************************
Zeit: Montag, 13. November 2023, 09.30 Uhr Ort: Informatikzentrum, E3, 2. Etage, Raum 9222
Referent: Henri Lotze M.Sc. Lehr- und Forschungsgebiet Theoretische Informatik
Thema: Going Offline -- Delays, Reservations and Predictions in Online Computation
Abstract:
The study of classical online computation builds upon a rather simple model. The input to a given problem is not known in advance, decisions have to made immediately upon the arrival of a new element and these decisions are irrevocable.
While this model is very well suitable to compute worst case bounds to a broad range of problems, there are some problems which are not well suited for this analysis. Naturally, problems that do not admit a constant approximation ratio in their offline formulation do not admit a constant competitive ratio in the worst case in the online formulation. However, some problems that are approximable still do not admit a constant competitive ratio when analyzed in the online case. For a subset of these problems, such as the Online Simple Knapsack problem and the class of general F-Node- and F-Edge-Deletion problems, the reason for this seems to be that a single, specific bad decision by an algorithm can be arbitrarily punished by an adversary.
In this talk, we explore modifications of the classical online model with the aim to find natural models that on the one hand cover a large range of problems and on the other hand work against pathological kinds of instances that restrict an algorithm from obtaining a constant competitive ratio. To this end, we study three modifications of the classical online model.
The models that we study are that of "Late Accepts" -- with Advice --, which allows to postpone decisions in online minimization problems until a current partial solution does not uphold a certain property anymore. The second one is that of "Reservations", in which any decision may be postponed for a cost proportional to the gain of an item. Finally, the model of "Bounded Predictions" allows an online algorithm to see the complete instance in advance, with a caveat: There is noise on the instance -- controlled by an adversary -- and each element may actually deviate from its prediction, up to factor that is known to the algorithm.
We are able to partially classify the advice complexity of the complete class of both F-Node-Deletion and F-Edge-Deletion problems. We give tight bounds on the competitive ratio for the Online Simple Knapsack problem with Reservations for the whole range of possible reservation costs, i.e. for a factor between 0 and 1. Finally, we give partially tight bounds for the Online Simple Knapsack problem with Bounded Predictions for the whole range of possible noise factors on the size of the items.
Es laden ein: die Dozentinnen und Dozenten der Informatik
Zeige Antworten nach Diskussionsstrang
+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +**********************************************************************
Zeit: Freitag, 15. Dezember 2023, 9.00 Uhr Ort: Raum 2202 (HBau, 2. Stock), Ahornstr. 55
Referent: Alexandru Kampmann M.Sc. RWTH Lehrstuhl Informatik 11
Thema: A Dynamic Service-oriented Software Architecture for the Automotive Domain
Abstract:
Today, almost all foreseeable areas of innovation in the automotive domain are software-driven. This development has led to the coining of the term Software-defined Vehicle (SDV), where the critical differentiator between competing OEMs becomes the software and not necessarily the hardware. Critical to this vision is the ability of the OEM to continuously provide software updates throughout the vehicle's lifetime.
Implementing SDVs requires novel architectures in almost all technical domains. For example, it is foreseeable that centralized high-performance computers communicating via real-time Ethernet will replace the multitude of distributed, customized ECUs in today's architectures. Most importantly, SDVs require novel, modular, and updatable software architectures to enable short development cycles and rapid time-to-market of software innovations.
This thesis presents ASOA, a software architecture for the automotive domain. While today's architectures are rigidly integrated at an early stage of development, ASOA follows the idea of dynamic runtime integration. The integration of software services in ASOA is dynamically established late in the development cycle - at the execution time of the system. Individual services are agnostic to the overall system, as an Orchestrator acts as the architecture controller that bundles system-specific knowledge. Continuous addition and modification of the software architecture are vital aspects of SDV vision. This agility is difficult to achieve with traditional architectures, where modifications to large parts of the systems are quickly required to perform architectural adaptions. In ASOA, these adaptations affect the Orchestrator and not necessarily individual services, which can be kept free of the details about the system they are part of.
ASOA distinguishes between functional orchestration and resource orchestration. Functional orchestration controls operating modes, data flow, and active services, allowing for dynamic architecture reconfiguration. In addition, functional orchestration supports the ad-hoc creation of redundant service structures and fault-tolerant execution of the Orchestrator. Resource orchestration provides methods for assigning compute cluster resources to the software services using multi-criteria optimization. It enables a reduction of the compute cluster power consumption and of the execution times of causality chains distributed across multiple services and ECU. ASOA also comes with a tool for system engineering that captures various views of the system architecture.
The portable implementation of ASOA enables transparent, API-identical execution of services on both Linux-based high-performance computers and resource-constrained microcontrollers with minimal operating systems. The implementation also enforces explicit dependencies between the consumption of computation time and data communication, both essential factors influencing the timing behavior of the software. Knowledge of these dependencies is critical to uncovering causality chains and functional dependencies. Various critical functions are implemented in full-scale vehicle prototypes using ASOA in the project UNICARagil.
Es laden ein: die Dozentinnen und Dozenten der Informatik
informatik-vortraege@lists.rwth-aachen.de
-
Henri Lotze -
Kampmann, Alexandru