Kaiserslautern - Fachbereich Mathematik
Refine
Year of publication
Document Type
- Report (106) (remove)
Language
- English (106) (remove)
Keywords
- Elastoplastizität (4)
- Elastoplasticity (3)
- Hysterese (3)
- Mathematikunterricht (3)
- Modellierung (3)
- modelling (3)
- praxisorientiert (3)
- Elastic BVP (2)
- Elastisches RWP (2)
- Elastoplastisches RWP (2)
- Inverses Problem (2)
- Jiang's model (2)
- Jiang-Modell (2)
- Lineare Algebra (2)
- Ratenunabhängigkeit (2)
- Regularisierung (2)
- Variationsungleichungen (2)
- Wavelet (2)
- algorithmic game theory (2)
- hysteresis (2)
- linear algebra (2)
- mathematical education (2)
- polynomial algorithms (2)
- praxis orientated (2)
- variational inequalities (2)
- (dynamic) network flows (1)
- Abstract linear systems theory (1)
- Automatische Differentiation (1)
- Bell Number (1)
- Berechnungskomplexität (1)
- Betriebsfestigkeit (1)
- Biot-Savart Operator (1)
- Biot-Savart operator (1)
- CHAMP <Satellitenmission> (1)
- Competitive Analysis (1)
- Continuum mechanics (1)
- Convex sets (1)
- Core (1)
- Differentialinklusionen (1)
- Dynamic Network Flows (1)
- Education (1)
- Elastoplastic BVP (1)
- FPTAS (1)
- Filippov theory (1)
- Filippov-Theorie (1)
- FlowLoc (1)
- Geomagnetic Field Modelling (1)
- Geomagnetismus (1)
- Geomathematik (1)
- Geostrophic flow (1)
- Gravimetrie (1)
- Greedy Heuristic (1)
- Green’s function (1)
- Helmholtz-Decomposition (1)
- Helmholtz-Zerlegung (1)
- Homotopie (1)
- Homotopiehochhebungen (1)
- Homotopy (1)
- Homotopy lifting (1)
- Hysteresis (1)
- Injectivity of mappings (1)
- Injektivität von Abbildungen (1)
- Inkorrekt gestelltes Problem (1)
- Jiang's constitutive model (1)
- Jiangsches konstitutives Gesetz (1)
- Kaktusgraph (1)
- Kontinuumsmechanik (1)
- Konvexe Mengen (1)
- Linear kinematic hardening (1)
- Linear kinematische Verfestigung (1)
- Lineare Optimierung (1)
- Locational Planning (1)
- Methode der Fundamentallösungen (1)
- Mie-Darstellung (1)
- Mie-Representation (1)
- Multi-dimensional systems (1)
- Nash equilibria (1)
- Nichtlineare/große Verformungen (1)
- Nonlinear/large deformations (1)
- One-dimensional systems (1)
- Online Algorithms (1)
- Parameter identification (1)
- Parameteridentifikation (1)
- Poroelastizität (1)
- Pseudopolynomial-Time Algorithm (1)
- Rate-independency (1)
- Restricted Shortest Path (1)
- SAW filters (1)
- SGG (1)
- SST (1)
- Satellitengradiometrie (1)
- Sensitivitäten (1)
- Shapley value (1)
- Shapleywert (1)
- Simplex (1)
- Spieltheorie (1)
- Standortplanung (1)
- Stop- and Play-Operators (1)
- Stop- und Play-Operator (1)
- Stop-und Play-Operator (1)
- Stücklisten (1)
- Theorie schwacher Lösungen (1)
- Train Rearrangement (1)
- Variational inequalities (1)
- Variationsungleichugen (1)
- Vectorial Wavelets (1)
- Vektor-Wavelets (1)
- Vektorkugelfunktionen (1)
- Vektorwavelets (1)
- automatic differentiation (1)
- autoregressive process (1)
- basic systems theoretic properties (1)
- bills of materials (1)
- bin coloring (1)
- cactus graph (1)
- change analysis (1)
- competitive analysis (1)
- complexity (1)
- cooperative game (1)
- core (1)
- delay management (1)
- differential inclusions (1)
- discrete time setting (1)
- durability (1)
- dynamic network flows (1)
- earliest arrival flows (1)
- eigenvalue problems (1)
- elastoplastic BVP (1)
- elastoplasticity (1)
- extreme equilibria (1)
- fptas (1)
- geomathematics (1)
- harmonic density (1)
- harmonische Dichte (1)
- heuristic (1)
- kooperative Spieltheorie (1)
- linear optimization (1)
- local approximation of sea surface topography (1)
- locally supported (Green’s) vector wavelets (1)
- locally supported wavelets (1)
- location theory (1)
- magnetic field (1)
- mechanism design (1)
- method of fundamental solutions (1)
- minimaler Schnittbaum (1)
- minimum cut tree (1)
- multiple objective optimization (1)
- network congestion game (1)
- neural network (1)
- nonparametric regression (1)
- online optimization (1)
- piezoelectric periodic surface acoustic wave filters (1)
- poroelasticity (1)
- price of anarchy (1)
- price of stability (1)
- public transportation (1)
- quickest path (1)
- rate-independency (1)
- robust network flows (1)
- selfish routing (1)
- sensitivities (1)
- sequential test (1)
- series-parallel graphs (1)
- simplex (1)
- single layer kernel (1)
- spherical decomposition (1)
- stop- and play-operators (1)
- strong equilibria (1)
- total latency (1)
- vector spherical harmonics (1)
- vectorial wavelets (1)
- wave propagation (1)
- weak solution theory (1)
- weakly/ strictly pareto optima (1)
Faculty / Organisational entity
Algebraic Systems Theory
(2004)
Control systems are usually described by differential equations, but their properties of interest are most naturally expressed in terms of the system trajectories, i.e., the set of all solutions to the equations. This is the central idea behind the so-called "behavioral approach" to systems and control theory. On the other hand, the manipulation of linear systems of differential equations can be formalized using algebra, more precisely, module theory and homological methods ("algebraic analysis"). The relationship between modules and systems is very rich, in fact, it is a categorical duality in many cases of practical interest. This leads to algebraic characterizations of structural systems properties such as autonomy, controllability, and observability. The aim of these lecture notes is to investigate this module-system correspondence. Particular emphasis is put on the application areas of one-dimensional rational systems (linear ODE with rational coefficients), and multi-dimensional constant systems (linear PDE with constant coefficients).
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.
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.
We compare different notions of differentiability of a measure along a vector field on a locally convex space. We consider in the \(L^2\)-space of a differentiable measure the analoga of the classical concepts of gradient, divergence and Laplacian (which coincides with the Ornstein-Uhlenbeck
operator in the Gaussian case). We use these operators for the extension of the basic results of Malliavin and Stroock on the smoothness of finite dimensional image measures under certain nonsmooth mappings to the case of non-Gaussian measures. The proof of this extension is quite direct and does not use any Chaos-decomposition. Finally, the role of this Laplacian in the
procedure of quantization of anharmonic oscillators is discussed.
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.
Hyperidentities
(1992)
The concept of a free algebra plays an essential role in universal algebra and in computer science. Manipulation of terms, calculations and the derivation of identities are performed in free algebras. Word problems, normal forms, system of reductions, unification and finite bases of identities are topics in algebra and logic as well as in computer science. A very fruitful point of view is to consider structural properties of free algebras. A.I. Malcev initiated a thorough research of the congruences of free algebras. Henceforth congruence permutable, congruence distributive and congruence modular varieties are
intensively studied. A lot of Malcev type theorems are connected to the congruence lattice of free algebras. Here we consider free algebras as semigroups of compositions of terms and more specific as clones of terms. The properties of these semigroups and clones are adequately described by hyperidentities. Naturally a lot of theorems of "semigroup" or "clone" type can be derived. This topic of research is still in its beginning and therefore a lot öf concepts and results cannot be presented in a final and polished form. Furthermore a lot of problems and questions are open which are of importance for the further development of the theory of hyperidentities.
On derived varieties
(1996)
Derived varieties play an essential role in the theory of hyperidentities. In [11] we have shown that derivation diagrams are a useful tool in the analysis of derived algebras and varieties. In this paper this tool is developed further in order to use it for algebraic constructions of derived algebras. Especially the operator \(S\) of subalgebras, \(H\) of homomorphic irnages and \(P\) of direct products are studied. Derived groupoids from the groupoid \(N or (x,y)\) = \(x'\wedge y'\) and from abelian groups are considered. The latter class serves as an example for fluid algebras and varieties. A fluid variety \(V\) has no derived variety as a subvariety and is introduced as a counterpart for solid varieties. Finally we use a property of the commutator of derived algebras in order to show that solvability and nilpotency are preserved under derivation.
A polynomial function \(f : L \to L\) of a lattice \(\mathcal{L}\) = \((L; \land, \lor)\) is generated by the identity function id \(id(x)=x\) and the constant functions \(c_a (x) = a\) (for every \(x \in L\)), \(a \in L\) by applying the operations \(\land, \lor\) finitely often. Every polynomial function in one or also in several variables is a monotone function of \(\mathcal{L}\).
If every monotone function of \(\mathcal{L}\)is a polynomial function then \(\mathcal{L}\) is called orderpolynomially complete. In this paper we give a new characterization of finite order-polynomially lattices. We consider doubly irreducible monotone functions and point out their relation to tolerances, especially to central relations. We introduce chain-compatible lattices
and show that they have a non-trivial congruence if they contain a finite interval and an infinite chain. The consequences are two new results. A modular lattice \(\mathcal{L}\) with a finite interval is order-polynomially complete if and only if \(\mathcal{L}\) is finite projective geometry. If \(\mathcal{L}\) is simple modular lattice of infinite length then every nontrivial interval is of infinite length and has the same cardinality as any other nontrivial interval of \(\mathcal{L}\). In the last sections we show the descriptive power of polynomial functions of
lattices and present several applications in geometry.
Order-semi-primal lattices
(1994)
Minimum Cut Tree Games
(2008)
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.
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.
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.