Improved algorithms for the multicut and multiflow problems in rooted trees

Costa et al. (Oper. Res. Lett. 31:21–27, 2003) presented a quadratic O(min (Kn,n ²)) greedy algorithm to solve the integer multicut and multiflow problems in a rooted tree. (n is the number of nodes of the tree, and K is the number of commodities). Their algorithm is a special case of the greedy type algorithm of Kolen (Location problems on trees and in the rectilinear plane. Ph.D. dissertation, 1982) to solve weighted covering and packing problems defined by general totally balanced (greedy) matrices. In this communication we improve the complexity bound in Costa et al. (Oper. Res. Lett. 31:21–27, 2003) and show that in the case of the integer multicut and multiflow problems in a rooted tree the greedy algorithm of Kolen can be implemented in subquadratic O(K+n+min (K,n)log n) time. The improvement is obtained by identifying additional properties of this model which lead to a subquadratic transformation to greedy form and using more sophisticated data structures.      

An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees

The problem of reconstructing the duplication tree of a set of tandemly repeated sequences which are supposed to have arisen by unequal recombination, was first introduced by Fitch (1977), and has recently received a lot of attention. In this paper, we place ourselves in a distance framework and deal with the restricted problem of reconstructing single copy duplication trees. We describe an exact and polynomial distance based algorithm for solving this problem, the parsimony version of which has previously been shown to be NP-hard (like most evolutionary tree reconstruction problems). This algorithm is based on the minimum evolution principle, and thus involves selecting the shortest tree as being the correct duplication tree. After presenting the underlying mathematical concepts behind the minimum evolution principle, and some of its benefits (such as statistical consistency), we provide a new recurrence formula to estimate the tree length using ordinary least-squares, given a matrix of pairwise distances between the copies. We then show how this formula naturally forms the dynamic programming framework on which our algorithm is based, and provide an implementation in O(n³) time and O(n²) space, where n is the number of copies.     

Dynamic evolution of economically preferred facilities

In a sustained development scenario, it is often the case that an investment is to be made over time in facilities that generate benefits. The benefits result from joint synergies between the facilities expressed as positive utilities specific to some subsets of facilities. As incremental budgets to finance fixed facility costs become available over time, additional facilities can be opened. The question is which facilities should be opened in order to guarantee that the overall benefit return over time is on the highest possible trajectory. This problem is common in situations such as ramping up a communication or transportation network where the facilities are hubs or service stations, or when introducing new technologies such as alternative fuels for cars and the facilities are fueling stations, or when expanding the production capacity with new machines, or when facilities are functions in a developing organization that is forced to make choices of where to invest limited funding.     

Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

A general model of parameterized OWA aggregation with given orness level

The paper proposes a general optimization model with separable strictly convex objective function to obtain the consistent OWA (ordered weighted averaging) operator family. The consistency means that the aggregation value of the operator monotonically changes with the given orness level. Some properties of the problem are discussed with its analytical solution. The model includes the two most commonly used maximum entropy OWA operator and minimum variance OWA operator determination methods as its special cases. The solution equivalence to the general minimax problem is proved. Then, with the conclusion that the RIM (regular increasing monotone quantifier) can be seen as the continuous case of OWA operator with infinite dimension, the paper further proposes a general RIM quantifier determination model, and analytically solves it with the optimal control technique. Some properties of the optimal solution and the solution equivalence to the minimax problem for RIM quantifier are also proved. Comparing with that of the OWA operator problem, the RIM quantifier solutions are usually more simple, intuitive, dimension free and can be connected to the linguistic terms in natural language. With the solutions of these general problems, we not only can use the OWA operator or RIM quantifier to obtain aggregation value that monotonically changes with the orness level for any aggregated set, but also can obtain the parameterized OWA or RIM quantifier families in some specific function forms, which can incorporate the background knowledge or the required characteristic of the aggregation problems.     

Minimum-Time Travel for a Vehicle with Acceleration Limits: Theoretical Analysis and Receding-Horizon Implementation

A methodology is proposed to generate minimum-time optimal velocity profiles for a vehicle with prescribed acceleration limits along a specified path. The necessary optimality conditions are explicitly derived, allowing the construction of the optimal solution semianalytically. A receding horizon implementation is also proposed for the on-line implementation of the velocity optimizer. Robustness of the receding horizon algorithm is guaranteed by the use of an adaptive scheme that determines the planning and execution horizons. Application to a real-life scenario with a comparison between the infinite and finite receding horizon schemes provides a validation of the proposed methodology. This work has been supported in part by the US Army Research Office, Awards DAAD19-00-1-0473 and W911NF-05-1-0331. The authors thank an anonymous reviewer for his insightful comments regarding the results in Sect. 5.     

An exact minimum variance filter for a class of discrete time systems with random parameter perturbations

An exact, closed-form minimum variance filter is designed for a class of discrete time uncertain systems which allows for both multiplicative and additive noise sources. The multiplicative noise model includes a popular class of models (Cox-Ingersoll-Ross type models) in econometrics. The parameters of the system under consideration which describe the state transition are assumed to be subject to stochastic uncertainties. The problem addressed is the design of a filter that minimizes the trace of the estimation error variance. Sensitivity of the new filter to the size of parameter uncertainty, in terms of the variance of parameter perturbations, is also considered. We refer to the new filter as the ‘perturbed Kalman filter’ (PKF) since it reduces to the traditional (or unperturbed) Kalman filter as the size of stochastic perturbation approaches zero. We also consider a related approximate filtering heuristic for univariate time series and we refer to filter based on this heuristic as approximate perturbed Kalman filter (APKF). We test the performance of our new filters on three simulated numerical examples and compare the results with unperturbed Kalman filter that ignores the uncertainty in the transition equation. Through numerical examples, PKF and APKF are shown to outperform the traditional (or unperturbed) Kalman filter in terms of the size of the estimation error when stochastic uncertainties are present, even when the size of stochastic uncertainty is inaccurately identified.     

A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem

In this paper we consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is a variation of the well-known Capacitated Vehicle Routing Problem (CVRP). In this problem, the traditional objective of minimizing total distance or time traveled by the vehicles is replaced by minimizing the sum of arrival times at the customers. We propose a branch-and-cut-and-price algorithm for obtaining optimal solutions to the problem. To the best of our knowledge, this is the first published exact algorithm for the CCVRP. We present computational results based on a set of standard CVRP benchmarks and investigate the effect of modifying the number of vehicles available.     

Minimum divergence estimators,maximum likelihood and exponential families

The dual representation formula of the divergence between two distributions in a parametric model is presented. Resulting estimators do not make use of any grouping or smoothing. For smooth divergences they all coincide with the MLE on any regular exponential family.     

A characterization of spaces of constant curvature by minimum covering radius of triangles

In this paper, we prove that if in a Riemannian manifold, the minimum covering radius of a point triple of small diameter depends only on the geodesic distances between the points, then the manifold must be of constant curvature. This implies that if in a complete connected Riemannian manifold, the volume of the intersection of three small geodesic balls of equal radii depends only on the distances between the centers and the radius, then it is one of the simply connected spaces of constant curvature. This generalizes an earlier result of the first author and D. Kunszenti-Kovács (2010).