KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 05 Dec 2018 15:08:25 +0100Wed, 05 Dec 2018 15:08:25 +0100SDE-driven modeling of phenotypically heterogeneous tumors: The influence of cancer cell stemness
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5426
We deduce cell population models describing the evolution of a tumor (possibly interacting with its
environment of healthy cells) with the aid of differential equations. Thereby, different subpopulations
of cancer cells allow accounting for the tumor heterogeneity. In our settings these include cancer
stem cells known to be less sensitive to treatment and differentiated cancer cells having a higher
sensitivity towards chemo- and radiotherapy. Our approach relies on stochastic differential equations
in order to account for randomness in the system, arising e.g., by the therapy-induced decreasing
number of clonogens, which renders a pure deterministic model arguable. The equations are deduced
relying on transition probabilities characterizing innovations of the two cancer cell subpopulations,
and similarly extended to also account for the evolution of normal tissue. Several therapy approaches
are introduced and compared by way of tumor control probability (TCP) and uncomplicated tumor
control probability (UTCP). A PDE approach allows to assess the evolution of tumor and normal
tissue with respect to time and to cell population densities which can vary continuously in a given set
of states. Analytical approximations of solutions to the obtained PDE system are provided as well.Julia Kroos; Christian Stinner; Christina Surulescu; Nicolae Surulescupreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5426Wed, 05 Dec 2018 15:08:25 +0100Multifacility Location Problems with Tree Structure and Finite Dominating Sets
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5156
Multifacility location problems arise in many real world applications. Often, the facilities can only be placed in feasible regions such as development or industrial areas. In this paper we show the existence of a finite dominating set (FDS) for the planar multifacility location problem with polyhedral gauges as distance functions, and polyhedral feasible regions, if the interacting facilities form a tree. As application we show how to solve the planar 2-hub location problem in polynomial time. This approach will yield an ε-approximation for the euclidean norm case polynomial in the input data and 1/ε.Andrea Maier; Thomas Ullmert; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5156Tue, 13 Feb 2018 14:47:15 +0100A local time stepping method for district heating networks
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5140
In this article a new numerical solver for simulations of district heating networks is presented. The numerical method applies the local time stepping introduced in [11] to networks of linear advection equations. In combination with the high order approach of [4] an accurate and very efficient scheme is developed. In several numerical test cases the advantages for simulations of district heating networks are shown.Raul Borsche; Matthias Eimer; Norbert Siedowpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5140Wed, 31 Jan 2018 08:05:43 +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 +0100Having a Plan B for Robust Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4585
We extend the standard concept of robust optimization by the introduction of an alternative solution. In contrast to the classic concept, one is allowed to chose two solutions from which the best can be picked after the uncertain scenario has been revealed. We focus in this paper on the resulting robust problem for combinatorial problems with bounded uncertainty sets. We present a reformulation of the robust problem which decomposes it into polynomially many subproblems. In each subproblem one needs to find two solutions which are connected by a cost function which penalizes if the same element is part of both solutions. Using this reformulation, we show how the robust problem can be solved efficiently for the unconstrained combinatorial problem, the selection problem, and the minimum spanning tree problem. The robust problem corresponding to the shortest path problem turns out to be NP-complete on general graphs. However, for series-parallel graphs, the robust shortest path problem can be solved efficiently. Further, we show how approximation algorithms for the subproblem can be used to compute approximate solutions for the original problem.André Chasseinpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4585Wed, 22 Feb 2017 14:40:39 +0100On a structured multiscale model for acid-mediated tumor invasion: the effects of adhesion and proliferation
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4488
We propose a multiscale model for tumor cell migration in a tissue network. The system of equations involves a structured population model for the tumor cell density, which besides time and
position depends on a further variable characterizing the cellular state with respect to the amount
of receptors bound to soluble and insoluble ligands. Moreover, this equation features pH-taxis and
adhesion, along with an integral term describing proliferation conditioned by receptor binding. The
interaction of tumor cells with their surroundings calls for two more equations for the evolution of
tissue fibers and acidity (expressed via concentration of extracellular protons), respectively. The
resulting ODE-PDE system is highly nonlinear. We prove the global existence of a solution and
perform numerical simulations to illustrate its behavior, paying particular attention to the influence
of the supplementary structure and of the adhesion.Christian Engwer; Christian Stinner; Christina Surulescupreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4488Fri, 11 Nov 2016 08:15:27 +0100On a coupled SDE-PDE system modeling acid-mediated tumor invasion
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4451
We propose and analyze a multiscale model for acid-mediated tumor invasion
accounting for stochastic effects on the subcellular level.
The setting involves a PDE of reaction-diffusion-taxis type describing the evolution of the tumor cell density,
the movement being directed towards pH gradients in the local microenvironment,
which is coupled to a PDE-SDE system characterizing the
dynamics of extracellular and intracellular proton concentrations, respectively.
The global well-posedness of the model is shown and
numerical simulations are performed in order to illustrate the solution behavior.Sandesh Athni Hiremath; Anna Zhigun; Stefanie Sonner; Christina Surulescupreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4451Thu, 22 Sep 2016 08:23:05 +0200Treatment of Reissner–Mindlin shells with kinks without the need for drilling rotation stabilization in an isogeometric framework
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4448
This work presents a framework for the computation of complex geometries containing intersections of multiple patches with Reissner-Mindlin shell elements. The main objective is to provide an isogeometric finite element implementation which neither requires drilling rotation stabilization, nor user interaction to quantify the number of rotational degrees of freedom for every node. For this purpose, the following set of methods is presented. Control points with corresponding physical location are assigned to one common node for the finite element solution. A nodal basis system in every control point is defined, which ensures an exact interpolation of the director vector throughout the whole domain. A distinction criterion for the automatic quantification of rotational degrees of freedom for every node is presented. An isogeometric Reissner-Mindlin shell formulation is enhanced to handle geometries with kinks and allowing for arbitrary intersections of patches. The parametrization of adjacent patches along the interface has to be conforming. The shell formulation is derived from the continuum theory and uses a rotational update scheme for the current director vector. The nonlinear kinematic allows the computation of large deformations and large rotations. Two concepts for the description of rotations are presented. The first one uses an interpolation which is commonly used in standard Lagrange-based shell element formulations. The second scheme uses a more elaborate concept proposed by the authors in prior work, which increases the accuracy for arbitrary curved geometries. Numerical examples show the high accuracy and robustness of both concepts. The applicability of the proposed framework is demonstrated.Wolfgang Dornisch; Sven Klinkelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4448Fri, 16 Sep 2016 12:50:46 +0200Isogeometric Reissner–Mindlin shell analysis with exactly calculated director vectors
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4447
An isogeometric Reissner-Mindlin shell derived from the continuum theory is presented. The geometry is described by NURBS surfaces. The kinematic description of the employed shell theory requires the interpolation of the director vector and of a local basis system. Hence, the definition of nodal basis systems at the control points is necessary for the proposed formulation. The control points are in general not located on the shell reference surface and thus, several choices for the nodal values are possible. The proposed new method uses the higher continuity of the geometrical description to calculate nodal basis system and director vectors which lead to geometrical exact interpolated values thereof. Thus, the initial director vector coincides with the normal vector even for the coarsest mesh. In addition to that a more accurate interpolation of the current director and its variation is proposed. Instead of the interpolation of nodal director vectors the new approach interpolates nodal rotations. Account is taken for the discrepancy between interpolated basis systems and the individual nodal basis systems with an additional transformation. The exact evaluation of the initial director vector along with the interpolation of the nodal rotations lead to a shell formulation which yields precise results even for coarse meshes. The convergence behavior is shown to be correct for k-refinement allowing the use of coarse meshes with high orders of NURBS basis functions. This is potentially advantageous for applications with high numerical effort per integration point. The geometrically nonlinear formulation accounts for large rotations. The consistent tangent matrix is derived. Various standard benchmark examples show the superior accuracy of the presented shell formulation. A new benchmark designed to test the convergence behavior for free form surfaces is presented. Despite the higher numerical effort per integration point the improved accuracy yields considerable savings in computation cost for a predefined error bound.Wolfgang Dornisch; Sven Klinkel; Bernd Simeonpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4447Mon, 12 Sep 2016 10:12:58 +0200The weak substitution method – An application of the mortar method for patch coupling in NURBS-based isogeometric analysis
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4436
In this contribution a mortar-type method for the coupling of non-conforming NURBS surface patches is proposed. The connection of non-conforming patches with shared degrees of freedom requires mutual refinement, which propagates throughout the whole patch due to the tensor-product structure of NURBS surfaces. Thus, methods to handle non-conforming meshes are essential in NURBS-based isogeometric analysis. The main objective of this work is to provide a simple and efficient way to couple the individual patches of complex geometrical models without altering the variational formulation. The deformations of the interface control points of adjacent patches are interrelated with a master-slave relation. This relation is established numerically using the weak form of the equality of mutual deformations along the interface. With the help of this relation the interface degrees of freedom of the slave patch can be condensated out of the system. A natural connection of the patches is attained without additional terms in the weak form. The proposed method is also applicable for nonlinear computations without further measures. Linear and geometrical nonlinear examples show the high accuracy and robustness of the new method. A comparison to reference results and to computations with the Lagrange multiplier method is given.Wolfgang Dornisch; Gennaro Vitucci; Sven Klinkelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4436Fri, 09 Sep 2016 08:57:48 +0200Global existence for a degenerate haptotaxis model of tumor invasion under the go-or-grow dichotomy hypothesis
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4384
We propose and study a strongly coupled PDE-ODE-ODE system modeling cancer cell invasion through a tissue network
under the go-or-grow hypothesis asserting that cancer cells can either move or proliferate. Hence our setting features
two interacting cell populations with their mutual transitions and involves tissue-dependent degenerate diffusion and
haptotaxis for the moving subpopulation. The proliferating cells and the tissue evolution are characterized by way of ODEs
for the respective densities. We prove the global existence of weak solutions and illustrate the model behaviour by
numerical simulations in a two-dimensional setting.Anna Zhigun; Christina Surulescu; Alexander Huntpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4384Tue, 31 May 2016 08:55:45 +0200Approximation of Ellipsoids Using Bounded Uncertainty Sets
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4344
In this paper, we discuss the problem of approximating ellipsoid uncertainty sets with bounded (gamma) uncertainty sets. Robust linear programs with ellipsoid uncertainty lead to quadratically constrained programs, whereas robust linear programs with bounded uncertainty sets remain linear programs which are generally easier to solve.
We call a bounded uncertainty set an inner approximation of an ellipsoid if it is contained in it. We consider two different inner approximation problems. The first problem is to find a bounded uncertainty set which sticks close to the ellipsoid such that a shrank version of the ellipsoid is contained in it. The approximation is optimal if the required shrinking is minimal. In the second problem, we search for a bounded uncertainty set within the ellipsoid with maximum volume. We present how both problems can be solved analytically by stating explicit formulas for the optimal solutions of these problems.
Further, we present in a computational experiment how the derived approximation techniques can be used to approximate shortest path and network flow problems which are affected by ellipsoidal uncertainty.André Chasseinpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4344Wed, 23 Mar 2016 16:01:15 +0100Nonsmooth Contact Dynamics for the Large-Scale Simulation of Granular Material
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4305
For the prediction of digging forces from a granular material simulation, the
Nonsmooth Contact Dynamics Method is examined. First, the equations of motion
for nonsmooth mechanical systems are laid out. They are a differential
variational inequality that has the same structure as classical discrete algebraic equations. Using a Galerkin projection in time, it becomes possible to derive
nonsmooth versions of the classical SHAK and RATTLE integrators.
A matrix-free Interior Point Method is used for the complementarity
problems that need to be solved in every time step. It is shown that this method
outperforms the Projected Gauss-Jacobi method by several orders of magnitude
and produces the same digging force result as the Discrete Element Method in comparable computing time.Jan Kleinert; Bernd Simeon; Klaus Dresslerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4305Wed, 24 Feb 2016 15:37:37 +0100Zone-based, Robust Flood Evacuation Planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4297
We consider the problem to evacuate several regions due to river flooding, where sufficient time is given to plan ahead. To ensure a smooth evacuation procedure, our model includes the decision which regions to assign to which shelter, and when evacuation orders should be issued, such that roads do not become congested.
Due to uncertainty in weather forecast, several possible scenarios are simultaneously considered in a robust optimization framework. To solve the resulting integer program, we apply a Tabu search algorithm based on decomposing the problem into better tractable subproblems. Computational experiments on random instances and an instance based on Kulmbach, Germany, data show considerable improvement compared to an MIP solver provided with a strong starting solution.Sabine Büttner; Marc Goerigkpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4297Wed, 03 Feb 2016 11:29:07 +0100Ranking Robustness and its Application to Evacuation Planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4296
We present a new approach to handle uncertain combinatorial optimization problems that uses solution ranking procedures to determine the degree of robustness of a solution. Unlike classic concepts for robust optimization, our approach is not purely based on absolute quantitative performance, but also includes qualitative aspects that are of major importance for the decision maker.
We discuss the two variants, solution ranking and objective ranking robustness, in more detail, presenting problem complexities and solution approaches. Using an uncertain shortest path problem as a computational example, the potential of our approach is demonstrated in the context of evacuation planning due to river flooding.Marc Goerigk; Horst Hamacher; Anika Kinscherffpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4296Wed, 03 Feb 2016 11:26:20 +0100Global existence for a go-or-grow multiscale model for tumor invasion with therapy
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4294
We investigate a PDE-ODE system describing cancer cell invasion in a tissue network. The model is an extension of the multiscale setting in [28,40], by considering two subpopulations of tumor cells interacting mutually and with the surrounding tissue. According to the go-or-grow hypothesis, these subpopulations consist of moving and proliferating cells, respectively. The mathematical setting also accommodates the effects of some therapy approaches. We prove the global existence of weak solutions to this model and perform numerical simulations to illustrate its behavior for different therapy strategies.Christian Stinner; Christina Surulescu; Aydar Uataypreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4294Mon, 01 Feb 2016 09:21:08 +0100Global existence for a degenerate haptotaxis model of cancer invasion
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4232
We propose and study a strongly coupled PDE-ODE system with tissue-dependent degenerate diffusion and haptotaxis that can serve as a model prototype for cancer cell invasion through the
extracellular matrix. We prove the global existence of weak solutions and illustrate the model behaviour by numerical simulations for a two-dimensional setting.Anna Zhigun; Christina Surulescu; Aydar Uataypreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4232Mon, 30 Nov 2015 08:35:47 +0100Performance Analysis in Robust Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4227
We discuss the problem of evaluating a robust solution.
To this end, we first give a short primer on how to apply robustification approaches to uncertain optimization problems using the assignment problem and the knapsack problem as illustrative examples.
As it is not immediately clear in practice which such robustness approach is suitable for the problem at hand,
we present current approaches for evaluating and comparing robustness from the literature, and introduce the new concept of a scenario curve. Using the methods presented in this paper, an easy guide is given to the decision maker to find, solve and compare the best robust optimization method for his purposes.André Chassein; Marc Goerigkpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4227Wed, 18 Nov 2015 08:25:22 +0100Minimizing the Number of Apertures in Multileaf Collimator Sequencing with Field Splitting
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4206
In this paper we consider the problem of decomposing a given integer matrix A into
a positive integer linear combination of consecutive-ones matrices with a bound on the
number of columns per matrix. This problem is of relevance in the realization stage
of intensity modulated radiation therapy (IMRT) using linear accelerators and multileaf
collimators with limited width. Constrained and unconstrained versions of the problem
with the objectives of minimizing beam-on time and decomposition cardinality are considered.
We introduce a new approach which can be used to find the minimum beam-on
time for both constrained and unconstrained versions of the problem. The decomposition
cardinality problem is shown to be NP-hard and an approach is proposed to solve the
lexicographic decomposition problem of minimizing the decomposition cardinality subject
to optimal beam-on time.Horst W. Hamacher; Ines M. Raschendorfer; Davaatseren Baatar; Matthias Ehrgottpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4206Wed, 28 Oct 2015 14:33:01 +0100Robust storage loading problems with stacking and payload constraints
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4158
We consider storage loading problems where items with uncertain weights have
to be loaded into a storage area, taking into account stacking and
payload constraints. Following the robust optimization paradigm, we propose
strict and adjustable optimization models for finite and interval-based
uncertainties. To solve these problems, exact decomposition and heuristic
solution algorithms are developed.
For strict robustness, we also present a compact formulation based
on a characterization of worst-case scenarios.
Computational results show that computation times and algorithm
gaps are reasonable for practical applications.
Furthermore, we find that the robustness concepts show different
potential depending on the type of data being used.Marc Goerigk; Sigrid Knust; Xuan Thanh Lepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4158Tue, 18 Aug 2015 08:23:49 +0200Discrete Parallel Machine Makespan ScheLoc Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4129
Scheduling-Location (ScheLoc) Problems integrate the separate fields of
scheduling and location problems. In ScheLoc Problems the objective is to
find locations for the machines and a schedule for each machine subject to
some production and location constraints such that some scheduling object-
ive is minimized. In this paper we consider the Discrete Parallel Machine
Makespan (DPMM) ScheLoc Problem where the set of possible machine loc-
ations is discrete and a set of n jobs has to be taken to the machines and
processed such that the makespan is minimized. Since the separate location
and scheduling problem are both NP-hard, so is the corresponding ScheLoc
Problem. Therefore, we propose an integer programming formulation and
different versions of clustering heuristics, where jobs are split into clusters
and each cluster is assigned to one of the possible machine locations. Since
the IP formulation can only be solved for small scale instances we propose
several lower bounds to measure the quality of the clustering heuristics. Ex-
tensive computational tests show the efficiency of the heuristics.Corinna Heßler; Kaouthar Deghdakpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4129Tue, 28 Jul 2015 09:40:15 +0200A new solution approach for solving the 2-facility location problem in the plane with block norms
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4128
Motivated by the time-dependent location problem over T time-periods introduced in
Maier and Hamacher (2015) we consider the special case of two time-steps, which was shown
to be equivalent to the static 2-facility location problem in the plane. Geometric optimality
conditions are stated for the median objective. When using block norms, these conditions
are used to derive a polygon grid inducing a subdivision of the plane based on normal cones,
yielding a new approach to solve the 2-facility location problem in polynomial time. Combinatorial algorithms for the 2-facility location problem based on geometric properties are
deduced and their complexities are analyzed. These methods differ from others as they are
completely working on geometric objects to derive the optimal solution set.Andrea Maierpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4128Fri, 24 Jul 2015 11:31:09 +0200Competitive Algorithms for Multistage Online Scheduling
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4119
We study an online flow shop scheduling problem where each job consists of several tasks that have to be completed in t different stages and the goal is to maximize the total weight of accepted jobs.
The set of tasks of a job contains one task for each stage and each stage has a dedicated set of identical parallel machines corresponding to it that can only process tasks of this stage. In order to gain the weight (profit) associated with a job j, each of its tasks has to be executed between a task-specific release date and deadline subject to the constraint that all tasks of job j from stages 1, …, i-1 have to be completed before the task of the ith stage can be started. In the online version, jobs arrive over time and all information about the tasks of a job becomes available at the release date of its first task. This model can be used to describe production processes in supply chains when customer orders arrive online.
We show that even the basic version of the offline problem with a single machine in each stage, unit weights, unit processing times, and fixed execution times for all tasks (i.e., deadline minus release date equals processing time) is APX-hard. Moreover, we show that the approximation ratio of any polynomial-time approximation algorithm for this basic version of the problem must depend on the number t of stages.
For the online version of the basic problem, we provide a (2t-1)-competitive deterministic online algorithm and a matching lower bound. Moreover, we provide several (sometimes tight) upper and lower bounds on the competitive ratio of online algorithms for several generalizations of the basic problem involving different weights, arbitrary release dates and deadlines, different processing times of tasks, and several identical machines per stage.Michael Hopf; Clemens Thielen; Oliver Wendtpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4119Thu, 09 Jul 2015 14:06:19 +0200On the History of Differential-Algebraic Equations
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4106
To write about the history of a subject is a challenge that grows with the number of pages as the original goal of completeness is turning more and more into an impossibility. With this in mind, the present article takes a very narrow approach and uses personal side trips and memories on conferences,
workshops, and summer schools as the stage for some of the most important protagonists and their contributions to the field of Differential-Algebraic Equations (DAEs).Bernd Simeonpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4106Tue, 23 Jun 2015 14:32:01 +0200