## Report in Wirtschaftsmathematik (WIMA Report)

### Refine

#### Year of publication

- 2011 (10) (remove)

#### Keywords

- autoregressive process (3)
- neural network (2)
- nonparametric regression (2)
- (dynamic) network flows (1)
- CUSUM statistic (1)
- Change analysis (1)
- Dynamic Network Flows (1)
- FPTAS (1)
- FlowLoc (1)
- INGARCH (1)

- 140
- Variants of the Shortest Path Problem (2011)
- 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.

- 133
- On a Cardinality Constrained Multicriteria Knapsack Problem (2011)
- 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.

- 135
- Reliable and Restricted Quickest Path Problems (2011)
- 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.

- 142
- An online approach to detecting changes in nonlinear autoregressive models (2011)
- 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.

- 137
- Testing for parameter stability in nonlinear autoregressive models (2011)
- 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.

- 138
- A uniform central limit theorem for neural network based autoregressive processes with applications to change-point analysis (2011)
- 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.

- 139
- Asymptotic order of the parallel volume difference (2011)
- 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.

- 136
- The Multi Terminal q-FlowLoc Problem: A Heuristic (2011)
- 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.

- 141
- Changepoint tests for INARCH time series (2011)
- 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.