## Report in Wirtschaftsmathematik (WIMA Report)

### Refine

#### Year of publication

#### Document Type

- Preprint (138)
- Report (16)
- Article (2)
- Working Paper (1)

#### Keywords

- 152
- A coverage-based Box-Algorithm to compute a representation for optimization problems with three objective functions (2014)
- 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.

- 151
- Optimization Models to Enhance Resilience in Evacuation Planning (2014)
- 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.

- 150
- Hierarchical Edge Colorings and Rehabilitation Therapy Planning in Germany (2014)
- 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.

- 149
- Edgeworth expansions for lattice triangular arrays (2014)
- 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.

- 148
- Monitoring time series based on estimating functions (2014)
- 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.

- 147
- On the Generality of the Greedy Algorithm for Solving Matroid Base Problems (2013)
- 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.

- 146
- Maximum Likelihood Estimators for Multivariate Hidden Markov Mixture Models (2013)
- 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.

- 145
- The Generalized Assignment Problem with Minimum Quantities (2012)
- 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.

- 144
- A limitation of the estimation of intrinsic volumes via pixel configuration counts (2012)
- 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.

- 143
- Complexity and Approximability of the Maximum Flow Problem with Minimum Quantities (2012)
- 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.