KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Sun, 03 May 2015 14:56:26 +0100Sun, 03 May 2015 14:56:26 +0100A Finite Dominating Set Algorithm for a Dynamic Location Problem in the Plane
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4017
A single facility problem in the plane is considered, where an optimal location has to be
identified for each of finitely many time-steps with respect to time-dependent weights and
demand points. It is shown that the median objective can be reduced to a special case of the
static multifacility median problem such that results from the latter can be used to tackle the
dynamic location problem. When using block norms as distance measure between facilities,
a Finite Dominating Set (FDS) is derived. For the special case with only two time-steps, the
resulting algorithm is analyzed with respect to its worst-case complexity. Due to the relation
between dynamic location problems for T time periods and T-facility problems, this algorithm
can also be applied to the static 2-facility location problem.Andrea Maier; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4017Thu, 05 Mar 2015 14:56:26 +0100Transit Dependent Evacuation Planning for Kathmandu Valley: A Case Study
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3944
Due to the increasing number of natural or man-made disasters, the application of operations research methods in evacuation planning has seen a rising interest in the research community. From the beginning, evacuation planning has been highly focused on car-based evacuation. Recently, also the evacuation of transit depended evacuees with the help of buses has been considered.
In this case study, we apply two such models and solution algorithms to evacuate a core part of the metropolitan capital city Kathmandu of Nepal as a hypothetical endangered region, where a large part of population is transit dependent. We discuss the computational results for evacuation time under a broad range of possible scenarios, and derive planning suggestions for practitioners.Urmila Pyakurel; Marc Goerigk; Tanka Dhamala; Horst W. Hamacherreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3944Wed, 10 Dec 2014 14:11:41 +0100A coverage-based Box-Algorithm to compute a representation for optimization problems with three objective functions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3911
A new algorithm for optimization problems with three objective functions is presented which computes a representation for the set of nondominated points. This representation is guaranteed to have a desired coverage error and a bound on the number of iterations needed by the algorithm to meet this coverage error is derived. Since the representation does not necessarily contain nondominated points only, ideas to calculate bounds for the representation error are given. Moreover, the incorporation of domination during the algorithm and other quality measures are discussed.Tobias Kuhn; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3911Fri, 07 Nov 2014 10:55:37 +0100Optimization Models to Enhance Resilience in Evacuation Planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3897
We argue that the concepts of resilience in engineering science and robustness in mathematical optimization are strongly related. Using evacuation planning as an example application, we demonstrate optimization techniques to improve solution resilience. These include a direct modelling of the uncertainty for stochastic or robust optimization, as well as taking multiple objective functions into account.Marc Goerigk; Horst Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3897Thu, 16 Oct 2014 10:22:16 +0200Hierarchical Edge Colorings and Rehabilitation Therapy Planning in Germany
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3832
In this paper we give an overview on the system of rehabilitation clinics in Germany in general and the literature on patient scheduling applied to rehabilitation facilities in particular.
We apply a class-teacher model developed to this environment and then generalize it to meet some of the specific constraints of inpatient rehabilitation clinics. To this end we introduce a restricted edge coloring on undirected bipartite graphs which is called group-wise balanced. The problem considered is called patient-therapist-timetable problem with group-wise balanced constraints (PTTPgb). In order to specify weekly schedules further such that they produce a reasonable allocation to morning/afternoon (second level decision) and to the single periods (third level decision) we introduce (hierarchical PTTPgb). For the corresponding model, the hierarchical edge coloring problem, we present some first feasibility results. Ines M. Raschendorfer; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3832Tue, 22 Jul 2014 11:16:14 +0200Edgeworth expansions for lattice triangular arrays
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3765
Edgeworth expansions have been introduced as a generalization of the central limit theorem and allow to investigate the convergence properties of sums of i.i.d. random variables. We consider triangular arrays of lattice random vectors and obtain a valid Edgeworth expansion for this case. The presented results can be used, for example, to study the convergence behavior of lattice models.Alona Bockpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3765Wed, 26 Mar 2014 12:14:40 +0100Monitoring time series based on estimating functions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3693
A large class of estimators including maximum likelihood, least squares and M-estimators are based on estimating functions. In sequential change point detection related monitoring functions can be used to monitor new incoming observations based on an initial estimator, which is computationally efficient because possible numeric optimization is restricted to the initial estimation. In this work, we give general regularity conditions under which we derive the asymptotic null behavior of the corresponding tests in addition to their behavior under alternatives, where conditions become particularly simple for sufficiently smooth estimating and monitoring functions. These regularity conditions unify and even extend a large amount of existing procedures in the literature, while they also allow us to derive monitoring schemes in time series that have not yet been considered in the literature including non-linear autoregressive time series and certain count time series such as binary or Poisson autoregressive models. We do not assume that the estimating and monitoring function are equal or even of the same dimension, allowing for example to combine a non-robust but more precise initial estimator with a robust monitoring scheme. Some simulations and data examples illustrate the usefulness of the described procedures.Claudia Kirch; Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3693Wed, 29 Jan 2014 10:20:27 +0100On the Generality of the Greedy Algorithm for Solving Matroid Base Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3535
It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or \(k\)-sum objective functions. Lara Turner; Matthias Ehrgott; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3535Wed, 19 Jun 2013 08:27:31 +0200Maximum Likelihood Estimators for Multivariate Hidden Markov Mixture Models
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3480
In this paper we consider a multivariate switching model, with constant states means
and covariances. In this model, the switching mechanism between the basic states of
the observed time series is controlled by a hidden Markov chain. As illustration, under
Gaussian assumption on the innovations and some rather simple conditions, we prove
the consistency and asymptotic normality of the maximum likelihood estimates of the model parameters.Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3480Mon, 15 Apr 2013 17:29:52 +0200The Generalized Assignment Problem with Minimum Quantities
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3290
We consider a variant of the generalized assignment problem (GAP) where the amount of space used in each bin is restricted to be either zero (if the bin is not opened) or above a given lower bound (a minimum quantity). We provide several complexity results for different versions of the problem and give polynomial time exact algorithms and approximation algorithms for restricted cases.
For the most general version of the problem, we show that it does not admit a polynomial time approximation algorithm (unless P=NP), even for the case of a single bin. This motivates to study dual approximation algorithms that compute solutions violating the bin capacities and minimum quantities by a constant factor. When the number of bins is fixed and the minimum quantity of each bin is at least a factor \(\delta>1\) larger than the largest size of an item in the bin, we show how to obtain a polynomial time dual approximation algorithm that computes a solution violating the minimum quantities and bin capacities by at most a factor \(1-\frac{1}{\delta}\) and \(1+\frac{1}{\delta}\), respectively, and whose profit is at least as large as the profit of the best solution that satisfies the minimum quantities and bin capacities strictly.
In particular, for \(\delta=2\), we obtain a polynomial time (1,2)-approximation algorithm.Sven Krumke; Clemens Thielenarticlehttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3290Mon, 08 Oct 2012 15:25:13 +0200A limitation of the estimation of intrinsic volumes via pixel configuration counts
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3273
It is often helpful to compute the intrinsic volumes of a set of which only a pixel image is observed. A computational efficient approach, which is suggested by several authors and used in practice, is to approximate the intrinsic volumes by a linear functional of the pixel configuration histogram. Here we want to examine, whether there is an optimal way of choosing this linear functional, where we will use a quite natural optimality criterion that has already been applied successfully for the estimation of the surface area. We will see that for intrinsic volumes other than volume or surface area this optimality criterion cannot be used, since estimators which ignore the data and return constant values are optimal w.r.t. this criterion. This shows that one has to be very careful, when intrinsic volumes are approximated by a linear functional of the pixel configuration histogram.Jürgen Kampfpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3273Mon, 01 Oct 2012 15:52:05 +0200Complexity and Approximability of the Maximum Flow Problem with Minimum Quantities
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3181
We consider the maximum flow problem with minimum quantities (MFPMQ), which is a variant of the maximum flow problem where
the flow on each arc in the network is restricted to be either zero or above a given lower bound (a minimum quantity), which
may depend on the arc. This problem has recently been shown to be weakly NP-complete even on series-parallel graphs.
In this paper, we provide further complexity and approximability results for MFPMQ and several special cases.
We first show that it is strongly NP-hard to approximate MFPMQ on general graphs (and even bipartite graphs) within any positive factor.
On series-parallel graphs, however, we present a pseudo-polynomial time dynamic programming algorithm for the problem.
We then study the case that the minimum quantity is the same for each arc in the network and show that, under this restriction, the problem is still
weakly NP-complete on general graphs, but can be solved in strongly polynomial time on series-parallel graphs.
On general graphs, we present a \((2 - 1/\lambda) \)-approximation algorithm for this case, where \(\lambda\) denotes the common minimum quantity of all arcs.Clemens Thielen; Stephan Westphalarticlehttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3181Fri, 06 Jul 2012 10:39:47 +0200Asymptotic Order of the Parallel Volume Difference
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2912
In this paper we investigate the asymptotic behaviour of the parallel volume
of fixed non-convex bodies in Minkowski spaces as the distance \(r\) tends to infinity.
We will show that the difference of the parallel volume of the convex hull of a
body and the parallel volume of the body itself can at most have order \(r^{d-2}\) in a \(d\)-dimensional space. Then we will show that in Euclidean spaces this difference can at most have order \(r^{d-3}\). These results have several applications, e.g. we will use
them to compute the derivative of \(f_\mu(rK)\) in \(r = 0\), where \(f_\mu\) is the Wills functional
or a similar functional, \(K\) is a body and \(rK\) is the Minkowski-product of \(r\) and \(K\). Finally we present applications concerning Brownian paths and Boolean models and derive new proofs for formulae for intrinsic volumes.Jürgen Kampfpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2912Mon, 27 Feb 2012 10:09:25 +0100An online approach to detecting changes in nonlinear autoregressive models
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2772
In this paper we develop monitoring schemes for detecting structural changes
in nonlinear autoregressive models. We approximate the regression function by a
single layer feedforward neural network. We show that CUSUM-type tests based
on cumulative sums of estimated residuals, that have been intensively studied
for linear regression in both an offline as well as online setting, can be extended
to this model. The proposed monitoring schemes reject (asymptotically) the null
hypothesis only with a given probability but will detect a large class of alternatives
with probability one. In order to construct these sequential size tests the limit
distribution under the null hypothesis is obtained.Claudia Kirch; Joseph Tadjuidje Kamgaingreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2772Mon, 24 Oct 2011 10:46:14 +0000Changepoint tests for INARCH time series
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2725
In this paper, we discuss the problem of testing for a changepoint in the structure
of an integer-valued time series. In particular, we consider a test statistic
of cumulative sum (CUSUM) type for general Poisson autoregressions of order
1. We investigate the asymptotic behaviour of conditional least-squares estimates
of the parameters in the presence of a changepoint. Then, we derive the
asymptotic distribution of the test statistic under the hypothesis of no change,
allowing for the calculation of critical values. We prove consistency of the test,
i.e. asymptotic power 1, and consistency of the corresponding changepoint estimate.
As an application, we have a look at changepoint detection in daily
epileptic seizure counts from a clinical study.Jürgen Franke; Claudia Kirch; Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2725Mon, 12 Sep 2011 09:49:44 +0200Variants of the Shortest Path Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2713
The shortest path problem in which the \((s,t)\)-paths \(P\) of a given digraph \(G =(V,E)\) are compared with respect to the sum of their edge costs is one of the best known problems in combinatorial optimization. The paper is concerned with a number of variations of this problem having different objective functions like bottleneck, balanced, minimum deviation, algebraic sum, \(k\)-sum and \(k\)-max objectives, \((k_1, k_2)-max, (k_1, k_2)\)-balanced and several types of trimmed-mean objectives. We give a survey on existing algorithms and propose a general model for those problems not yet treated in literature. The latter is based on the solution of resource constrained shortest path problems with equality constraints which can be solved in pseudo-polynomial time if the given graph is acyclic and the number of resources is fixed. In our setting, however, these problems can be solved in strongly polynomial time. Combining this with known results on \(k\)-sum and \(k\)-max optimization for general combinatorial problems, we obtain strongly polynomial algorithms for a variety of path problems on acyclic and general digraphs. Lara Turnerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2713Thu, 25 Aug 2011 09:14:11 +0200Asymptotic order of the parallel volume difference
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2327
In this paper we continue the investigation of the asymptotic behavior of the parallel volume in Minkowski spaces as the distance tends to infinity that was started in [13]. We will show that the difference of the parallel volume of the convex hull of a body and the parallel volume of the body itself can at most have order \(r^{d-2}\) in dimension \(d\). Then we will show that in the Euclidean case this difference can at most have order \(r^{d-3}\). We will also examine the asymptotic behavior of the derivative of this difference as the distance tends to infinity. After this we will compute the derivative of \(f_\mu (rK)\) in \(r\), where \(f_\mu\) is the Wills functional or a similar functional, \(K\) is a fixed body and \(rK\) is the Minkowski-product of \(r\) and \(K\). Finally we will use these results to examine Brownian paths and Boolean models and derive new proofs for formulae for intrinsic volumes.Jürgen Kampfpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2327Thu, 26 May 2011 11:11:40 +0200A uniform central limit theorem for neural network based autoregressive processes with applications to change-point analysis
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2302
We consider an autoregressive process with a nonlinear regression function that is modeled by a feedforward neural network. We derive a uniform central limit theorem which is useful in the context of change-point analysis. We propose a test for a change in the autoregression function which - by the uniform central limit theorem - has asymptotic power one for a large class of alternatives including local alternatives.Claudia Kirch; Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2302Fri, 25 Mar 2011 14:44:40 +0100Testing for parameter stability in nonlinear autoregressive models
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2301
In this paper we develop testing procedures for the detection of structural changes in nonlinear autoregressive processes. For the detection procedure we model the regression function by a single layer feedforward neural network. We show that CUSUM-type tests based on cumulative sums of estimated residuals, that have been intensively studied for linear regression, can be extended to this case. The limit distribution under the null hypothesis is obtained, which is needed to construct asymptotic tests. For a large class of alternatives it is shown that the tests have asymptotic power one. In this case, we obtain a consistent change-point estimator which is related to the test statistics. Power and size are further investigated in a small simulation study with a particular emphasis on situations where the model is misspecified, i.e. the data is not generated by a neural network but some other regression function. As illustration, an application on the Nile data set as well as S&P log-returns is given.Claudia Kirch; Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2301Fri, 25 Mar 2011 14:44:06 +0100The Multi Terminal q-FlowLoc Problem: A Heuristic
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2290
In this paper the multi terminal q-FlowLoc problem (q-MT-FlowLoc) is introduced. FlowLoc problems combine two well-known modeling tools: (dynamic) network flows and locational analysis. Since the q-MT-FlowLoc problem is NP-hard we give a mixed integer programming formulation and propose a heuristic which obtains a feasible solution by calculating a maximum flow in a special graph H. If this flow is also a minimum cost flow, various versions of the heuristic can be obtained by the use of different cost functions. The quality of this solutions is compared.Stephanie Heller; Horst W. Hamacherreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2290Wed, 02 Mar 2011 16:46:24 +0100Reliable and Restricted Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288
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.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288Wed, 02 Mar 2011 16:45:38 +0100On a Cardinality Constrained Multicriteria Knapsack Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2281
We consider a variant of a knapsack problem with a fixed cardinality constraint. There are three objective functions to be optimized: one real-valued and two integer-valued objectives. We show that this problem can be solved efficiently by a local search. The algorithm utilizes connectedness of a subset of feasible solutions and has optimal run-time.Florian Seipp; Stefan Ruzika; Luis Paquetepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2281Tue, 08 Feb 2011 12:18:44 +0100Train Marshalling Problem - Algorithms and Bounds -
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2263
The Train Marshalling Problem consists of rearranging an incoming train in a marshalling yard in such a way that cars with the same destinations appear consecutively in the final train and the number of needed sorting tracks is minimized. Besides an initial roll-in operation, just one pull-out operation is allowed. This problem was introduced by Dahlhaus et al. who also showed that the problem is NP-complete. In this paper, we provide a new lower bound on the optimal objective value by partitioning an appropriate interval graph. Furthermore, we consider the corresponding online problem, for which we provide upper and lower bounds on the competitiveness and a corresponding optimal deterministic online algorithm. We provide an experimental evaluation of our lower bound and algorithm which shows the practical tightness of the results.Katharina Beygang; Sven O. Krumke; Florian Dahmsreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2263Mon, 10 Jan 2011 10:26:59 +0100Generalized Multiple Objective Bottleneck Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2252
We consider multiple objective combinatiorial optimization problems in which the first objective is of arbitrary type and the remaining objectives are either bottleneck or k-max objective functions. While the objective value of a bottleneck objective is determined by the largest cost value of any element in a feasible solution, the kth-largest element defines the objective value of the k-max objective. An efficient solution approach for the generation of the complete nondominated set is developed which is independent of the specific combinatiorial problem at hand. This implies a polynomial time algorithm for several important problem classes like shortest paths, spanning tree, and assignment problems with bottleneck objectives which are known to be NP-hard in the general multiple objective case.Jochen Gorski; Kathrin Klamroth; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2252Thu, 09 Dec 2010 10:21:17 +0100Min-Max Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249
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.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249Fri, 19 Nov 2010 09:57:06 +0100