KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Tue, 12 Dec 2017 08:18:05 +0100Tue, 12 Dec 2017 08:18:05 +0100Having a Plan B for Robust Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5097
We continue in this paper the study of k-adaptable robust solutions for combinatorial optimization problems with bounded uncertainty sets. In this concept not a single solution needs to be chosen to hedge against the uncertainty. Instead one is allowed to choose a set of k different solutions from which one can be chosen after the uncertain scenario has been revealed. We first show how the problem can be decomposed into polynomially many subproblems if k is fixed. In the remaining part of the paper we consider the special case where k=2, i.e., one is allowed to choose two different solutions to hedge against the uncertainty. We decompose this problem into so called coordination problems. The study of these coordination problems turns out to be interesting on its own. We prove positive results for the unconstrained combinatorial optimization problem, the matroid maximization problem, the selection problem, and the shortest path problem on series parallel graphs. The shortest path problem on general graphs turns out to be NP-complete. Further, we present for minimization problems how to transform approximation algorithms for the coordination problem to approximation algorithms for the original problem. We study the knapsack problem to show that this relation does not hold for maximization problems in general. We present a PTAS for the corresponding coordination problem and prove that the 2-adaptable knapsack problem is not at all approximable.André Chasseinpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5097Tue, 12 Dec 2017 08:18:05 +0100Duty Rostering for Physicians at a Department of Orthopedics and Trauma Surgery
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5081
This paper presents a case study of duty rostering for physicians at a department of orthopedics and trauma surgery. We provide a detailed description of the rostering problem faced and present an integer programming model that has been used in practice for creating duty rosters at the department for more than a year. Using real world data, we compare the model output to a manually generated roster as used previously by the department and analyze the quality of the rosters generated by the model over a longer time span. Moreover, we demonstrate how unforeseen events such as absences of scheduled physicians are handled.Clemens Thielenpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5081Mon, 04 Dec 2017 10:58:44 +0100Order-semi-primal lattices
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5073
Dietmar Schweigertreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5073Fri, 10 Nov 2017 14:43:42 +0100Representations by order-polynomially complete lattices
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5072
Bernd Kilgus; Dietmar Schweigertreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5072Fri, 10 Nov 2017 14:38:25 +0100Strictly order primal algebras
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5071
Otfried Lüders; Dietmar Schweigertreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5071Fri, 10 Nov 2017 14:33:13 +0100Pre-fixed points of polynomial functions in lattices
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5070
Marcel Erne; Dietmar Schweigertreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5070Fri, 10 Nov 2017 14:25:34 +0100Domain decomposition for kinetic problems with strongly contrasted Knudsen numbers
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5069
A nonequilibrium situation governed by kinetic equations with strongly contrasted Knudsen numbers in different subdomains is discussed. We consider a domain decomposition problem for Boltzmann- and Euler equations, establish the correct coupling conditions and prove the validity of the obtained coupled solution . Moreover numerical examples comparing different types of coupling conditions are presented.Axel Klarreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5069Fri, 10 Nov 2017 14:20:20 +0100Projective resolutions associated to projections
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5066
Theo de Jong; Duco van Stratenreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5066Fri, 10 Nov 2017 13:00:48 +0100Conjugated operatorideals and the \(\mathcal{A}-\)Local reflexivity principle
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5065
Frank Oertelreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5065Fri, 10 Nov 2017 12:54:35 +0100Regularized approximation methods with perturbations for ill-posed operator equations
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5064
We are concerned with a parameter choice strategy for the Tikhonov regularization \((\tilde{A}+\alpha I)\tilde{x}\) = T* \(\tilde{y}\)+ w where \(\tilde{A}\) is a (not necessarily selfadjoint) approximation of T*T and T*\(\tilde y\)+ w is a perturbed form of the (not exactly computed) term T*y. We give conditions for convergence and optimal convergence rates.M. Thamban Nair; Eberhard Schockreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5064Fri, 10 Nov 2017 11:57:22 +0100On the Convergence at lnfinity of Solutions with Finite Dirichlet Integral to the Exterior Dirichlet Problem for the Steady Plane Navier-Stokes System of Equations
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5061
Dan Socolescureporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5061Fri, 10 Nov 2017 09:55:59 +0100Polynomial functions of modular lattices
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5060
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.Dietmar Schweigertreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5060Fri, 10 Nov 2017 09:47:24 +0100On derived varieties
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5059
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.Dietmar Schweigertreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5059Fri, 10 Nov 2017 09:22:23 +0100The Tangent Space at a Special Sympletic Instanton Bundle on \(P_{2n+1}\)
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5058
Giorgio Ottaviani; Günther Trautmannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5058Thu, 09 Nov 2017 15:32:15 +0100Error estimates for Tikhonov regularization with unbounded regularizing operators
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5056
It is shown that Tikhonov regularization for ill- posed operator equation
\(Kx = y\) using a possibly unbounded regularizing operator \(L\) yields an orderoptimal algorithm with respect to certain stability set when the regularization parameter is chosen according to the Morozov's discrepancy principle. A more realistic error estimate is derived when the operators \(K\) and \(L\) are related to a Hilbert scale in a suitable manner. The result includes known error estimates for ordininary Tikhonov regularization and also the estimates available under the Hilbert scale approach.M. Thamban Nairreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5056Thu, 09 Nov 2017 12:01:16 +0100The moduli scheme M(0,2,4) over \(\mathbb{P}_3\)
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5054
Rosa Maria Miro-Roig; Günther Trautmannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5054Thu, 09 Nov 2017 11:52:42 +0100On the Variance of the Number of Pivot Steps Required by the Simplex Algorithm
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5053
The article provides an asymptotic probabilistic analysis of the variance of the number of pivot steps required by phase II of the "shadow vertex algorithm" - a parametric variant of the simplex algorithm, which has been proposed by Borgwardt [1] . The analysis is done for data which satisfy a rotationally
invariant distribution law in the \(n\)-dimensional unit ball.Karl-Heinz Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5053Thu, 09 Nov 2017 11:28:09 +0100On the Variance of Additive Random Variables on Stochastic Polyhedra
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5052
Let \(a_i i:= 1,\dots,m.\) be an i.i.d. sequence taking values in \(\mathbb{R}^n\). Whose convex hull is interpreted as a stochastic polyhedron \(P\). For a special class of random variables which decompose additively relative to their boundary simplices, eg. the volume of \(P\), integral representations of their first two moments are given which lead to asymptotic estimations of variances for special "additive variables" known from stochastic approximation theory in case of rotationally symmetric distributions.Karl-Heinz Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5052Thu, 09 Nov 2017 11:14:30 +0100On the expected number of shadow vertices of the convex hull of random points
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5051
Let \(a_1,\dots,a_m\) be independent random points in \(\mathbb{R}^n\) that are independent and identically distributed spherically symmetrical in \(\mathbb{R}^n\). Moreover, let \(X\) be the random polytope generated as the convex hull of \(a_1,\dots,a_m\) and let \(L_k\) be an arbitrary \(k\)-dimensional
subspace of \(\mathbb{R}^n\) with \(2\le k\le n-1\). Let \(X_k\) be the orthogonal projection image of \(X\) in \(L_k\). We call those vertices of \(X\), whose projection images in \(L_k\) are vertices of \(X_k\)as well shadow vertices of \(X\) with respect to the subspace \(L_k\) . We derive a distribution independent sharp upper bound for the expected number of shadow vertices of \(X\) in \(L_k\).Karl-Heinz Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5051Thu, 09 Nov 2017 10:49:33 +0100On the Approximation of a Ball by Random Polytopes
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5050
Let (\(a_i)_{i\in \bf{N}}\) be a sequence of identically and independently distributed random vectors drawn from the \(d\)-dimensional unit ball \(B^d\)and let \(X_n\):= convhull \((a_1,\dots,a_n\)) be the random polytope generated by \((a_1,\dots\,a_n)\). Furthermore, let \(\Delta (X_n)\) : = (Vol \(B^d\) \ \(X_n\)) be the deviation of the polytope's volume from the volume of the ball. For uniformly distributed \(a_i\) and \(d\ge2\), we prove that tbe limiting distribution of \(\frac{\Delta (X_n)} {E(\Delta (X_n))}\) for \(n\to\infty\) satisfies a 0-1-law. Especially, we provide precise information about the asymptotic behaviour of the variance of \(\Delta (X_n\)). We deliver analogous results for spherically symmetric distributions in \(B^d\) with regularly varying tail.Karl-Heinz Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5050Thu, 09 Nov 2017 08:45:36 +0100An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5049
Let \(a_1,\dots,a_m\) be i.i .d. vectors uniform on the unit sphere in \(\mathbb{R}^n\), \(m\ge n\ge3\) and let \(X\):= {\(x \in \mathbb{R}^n \mid a ^T_i x\leq 1\)} be the random polyhedron generated by. Furthermore, for linearly independent vectors \(u\), \(\bar u\) in \(\mathbb{R}^n\), let \(S_{u, \bar u}(X)\) be the number of shadow vertices of \(X\) in \(span (u, \bar u\)). The paper provides an asymptotic expansion of the expectation value \(E (S_{u, \bar u})\) for fixed \(n\) and \(m\to\infty\). The first terms of the expansion are given explicitly. Our investigation of \(E (S_{u, \bar u})\) is closely connected to Borgwardt's probabilistic analysis of the shadow vertex algorithm - a parametric variant of the simplex algorithm. We obtain an improved asymptotic upper bound for the number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.Karl-Heinz Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5049Wed, 08 Nov 2017 16:03:14 +0100A Unified Asymptotic Prohabilistic Analysis of Polyhedral Functionals
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5048
Let \(A\):= {\(a_i\mid i= 1,\dots,m\)} be an i.i.d. random sample in (\mathbb{R}^n\), which we consider a random polyhedron, either as the convex hull of the \(a_i\) or as the intersection of halfspaces {\(x \mid a ^T_i x\leq 1\)}. We introduce a class of polyhedral functionals we will call "additive-type functionals", which covers a number of polyhedral functionals discussed in different mathematical fields, where the emphasis in our contribution will be on those, which arise in linear optimization theory. The class of additive-type functionals is a suitable setting in order to unify and to simplify the asymptotic probabilistic analysis of first and second moments of polyhedral functionals. We provide examples of asymptotic results on expectations and on variances.Karl-Heinz Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5048Wed, 08 Nov 2017 14:21:28 +0100A comparison method for expectations of a class of continuous polytope functionals
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5047
Let \(a_1,\dots,a_n\) be independent random points in \(\mathbb{R}^d\) spherically symmetrically but not necessarily identically distributed. Let \(X\) be the random polytope generated as the convex hull of \(a_1,\dots,a_n\) and for any \(k\)-dimensional subspace \(L\subseteq \mathbb{R}^d\) let \(Vol_L(X) :=\lambda_k(L\cap X)\) be the volume of \(X\cap L\) with respect to the \(k\)-dimensional Lebesgue measure \(\lambda_k, k=1,\dots,d\). Furthermore, let \(F^{(i)}\)(t):= \(\bf{Pr}\) \(\)(\(\Vert a_i \|_2\leq t\)),
\(t \in \mathbb{R}^+_0\) , be the radial distribution function of \(a_i\). We prove that the expectation
functional \(\Phi_L\)(\(F^{(1)}, F^{(2)},\dots, F^{(n)})\) := \(E(Vol_L(X)\)) is strictly decreasing in
each argument, i.e. if \(F^{(i)}(t) \le G^{(i)}(t)t\), \(t \in {R}^+_0\), but \(F^{(i)} \not\equiv G^{(i)}\), we show \(\Phi\) \((\dots, F^{(i)}, \dots\)) > \(\Phi(\dots,G^{(i)},\dots\)). The proof is clone in the more general framework
of continuous and \(f\)- additive polytope functionals.Karl-Heinz Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5047Wed, 08 Nov 2017 13:33:06 +0100A Simple Integral Representation for the Second Moments of Additive Random Variables on Stochastic Polyhedra
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5045
Let \(a_1, i:=1,\dots,m\), be an i.i.d. sequence taking values in \(\mathbb{R}^n\), whose convex hull is interpreted as a stochastic polyhedron \(P\). For a special class of random variables, which decompose additively relative to their boundary simplices, eg. the volume of \(P\), simple integral representations of its first two moments are given in case of rotationally symmetric distributions in order to facilitate estimations of variances or to quantify large deviations from the mean.Karl-Heinz Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5045Tue, 07 Nov 2017 15:52:54 +0100Ranking Approach to Max-Ordering Combinatorial Optimization and Network Flows
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5044
Max ordering (MO) optimization is introduced as tool for modelling production
planning with unknown lot sizes and in scenario modelling. In MO optimization a feasible solution set \(X\) and, for each \(x\in X, Q\) individual objective functions \(f_1(x),\dots,f_Q(x)\) are given. The max ordering objective
\(g(x):=max\) {\(f_1(x),\dots,f_Q(x)\)} is then minimized over all \(x\in X\).
The paper discusses complexity results and describes exact and approximative
algorithms for the case where \(X\) is the solution set of combinatorial
optimization problems and network flow problems, respectively.Claus Hüsselmann; Horst W. Hamacherreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5044Tue, 07 Nov 2017 15:32:36 +0100