KLUEDO RSS FeedNeueste Dokumente / Latest documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 26 Mar 2014 12:14:40 +0100Wed, 26 Mar 2014 12:14:40 +0100Edgeworth 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 +0100Efficient Computation of Equilibria in Bottleneck Games via Game Transformation
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2283
Thomas L. Werth; Heike Sperber; Sven O. Krumkereporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2283Thu, 10 Feb 2011 10:37:35 +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 +0100Dynamic Multi-Period Routing With Two Classes
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2228
In the Dynamic Multi-Period Routing Problem, one is given a new set of requests at the beginning of each time period. The aim is to assign requests to dates such that all requests are fulfilled by their deadline and such that the total cost for fulling the requests is minimized. We consider a generalization of the problem which allows two classes of requests: The 1st class requests can only be fulfilled by the 1st class server, whereas the 2nd class requests can be fulfilled by either the 1st or 2nd class server. For each tour, the 1st class server incurs a cost that is alpha times the cost of the 2nd class server, and in each period, only one server can be used. At the beginning of each period, the new requests need to be assigned to service dates. The aim is to make these assignments such that the sum of the costs for all tours over the planning horizon is minimized. We study the problem with requests located on the nonnegative real line and prove that there cannot be a deterministic online algorithm with a competitive ratio better than alpha. However, if we require the difference between release and deadline date to be equal for all requests, we can show that there is a min{2*alpha, 2 + 2/alpha}-competitive algorithm.Sven O. Krumke; Christiane Zeckreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2228Mon, 16 Aug 2010 15:41:41 +0200Universal Shortest Paths
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2230
We introduce the universal shortest path problem (Univ-SPP) which generalizes both - classical and new - shortest path problems. Starting with the definition of the even more general universal combinatorial optimization problem (Univ-COP), we show that a variety of objective functions for general combinatorial problems can be modeled if all feasible solutions have the same cardinality. Since this assumption is, in general, not satisfied when considering shortest paths, we give two alternative definitions for Univ-SPP, one based on a sequence of cardinality contrained subproblems, the other using an auxiliary construction to establish uniform length for all paths between source and sink. Both alternatives are shown to be (strongly) NP-hard and they can be formulated as quadratic integer or mixed integer linear programs. On graphs with specific assumptions on edge costs and path lengths, the second version of Univ-SPP can be solved as classical sum shortest path problem.Lara Turner; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2230Mon, 16 Aug 2010 11:00:30 +0200Online Delay Management
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2197
We present extensions to the Online Delay Management Problem on a Single Train Line. While a train travels along the line, it learns at each station how many of the passengers wanting to board the train have a delay of delta. If the train does not wait for them, they get delayed even more since they have to wait for the next train. Otherwise, the train waits and those passengers who were on time are delayed by delta. The problem consists in deciding when to wait in order to minimize the total delay of all passengers on the train line. We provide an improved lower bound on the competitive ratio of any deterministic online algorithm solving the problem using game tree evaluation. For the extension of the original model to two possible passenger delays delta_1 and delta_2, we present a 3-competitive deterministic online algorithm. Moreover, we study an objective function modeling the refund system of the German national railway company, which pays passengers with a delay of at least Delta a part of their ticket price back. In this setting, the aim is to maximize the profit. We show that there cannot be a deterministic competitive online algorithm for this problem and present a 2-competitive randomized algorithm.Sven O. Krumke; Clemens Thielen; Christiane Zeckreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2197Thu, 08 Jul 2010 08:52:34 +0200Weak Dependence of Functional INGARCH Processes
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2186
We introduce a class of models for time series of counts which include INGARCH-type models as well as log linear models for conditionally Poisson distributed data. For those processes, we formulate simple conditions for stationarity and weak dependence with a geometric rate. The coupling argument used in the proof serves as a role model for a similar treatment of integer-valued time series models based on other types of thinning operations.Jürgen Frankepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2186Thu, 15 Apr 2010 07:56:55 +0200