Quantile composite-based path modeling

The paper aims at introducing a quantile approach in the Partial Least Squares path modeling framework. This is a well known composite-based method for the analysis of complex phenomena measurable through a network of relationships among observed and unobserved variables. The proposal intends to enhance potentialities of the Partial Least Squares path models overcoming the classical exploration of average effects. The introduction of Quantile Regression and Correlation in the estimation phases of the model allows highlighting how and if the relationships among observed and unobserved variables change according to the explored quantile of interest. The proposed method is applied to two real datasets in the customer satisfaction measurement and in the sensory analysis framework but it proves to be useful also in other applicative contexts.     

Non-symmetrical composite-based path modeling

Partial least squares path modeling presents some inconsistencies in terms of coherence with the predictive directions specified in the inner model (i.e. the path directions), because the directions of the links in the inner model are not taken into account in the iterative algorithm. In fact, the procedure amplifies interdependence among blocks and fails to distinguish between dependent and explanatory blocks. The method proposed in this paper takes into account and respects the specified path directions, with the aim of improving the predictive ability of the model and to maintain the hypothesized theoretical inner model. To highlight its properties, the proposed method is compared to the classical PLS path modeling in terms of explained variability, predictive relevance and interpretation using artificial data through a real data application. A further development of the method allows to treat multi-dimensional blocks in composite-based path modeling.     

Proper deflating subspaces: properties,algorithms and applications

An algorithm for computing proper deflating subspaces with specified spectrum for an arbitrary matrix pencil is presented. The method uses refined algorithms for computing the generalized Schur form of a matrix pencil and enlightens the connection that exists between reducing and proper deflating subspaces. The proposed algorithm can be applied for computing the stabilizing solution of the generalized algebraic Riccati equation, a recently introduced concept which extends the usual algebraic Riccati equation.     

Lepp-bisection algorithms,applications and mathematical properties

Longest edge (nested) algorithms for triangulation refinement in two dimensions are able to produce hierarchies of quality and nested irregular triangulations as needed both for adaptive finite element methods and for multigrid methods for PDEs. In addition, right-triangle bintree triangulations are multiresolution algorithms used for terrain modeling and real time visualization of terrain applications. These algorithms are based on the properties of the consecutive bisection of a triangle by the median of the longest edge, and can be formulated in terms of the longest edge propagation path (Lepp) and terminal edge concepts, which implies the use of very local refinement operations over fully conforming meshes (where the intersection of pairs of neighbor triangles is either a common edge or a common vertex). In this paper we review the Lepp-bisection algorithms, their properties and applications. To the end we use recent simpler and stronger results on the complexity aspects of the bisection method and its geometrical properties. We discuss and analyze the computational costs of the algorithms. The generalization of the algorithms to 3-dimensions is also discussed. Applications of these methods are presented: for serial and parallel view dependent level of detail terrain rendering, and for the parallel refinement of tetrahedral meshes.     

Median spheres: theory, algorithms, applications

A generalized hypersphere is either a hyperplane or a hypersphere, which consists of all points equidistant from a center. Geometrically, a weighted median hypersphere minimizes a weighted average of the distances from it to finitely many data points. As proved here, for each finite data set there exists at least one weighted median generalized hypersphere. Moreover, denote the sums of the weights of the data points inside by W ⁻, outside by W ⁺, and on the hypersphere by W ⁰. The present results show that each weighted median hypersphere is a weighted pseudo-halving hypersphere, in the sense that |W ⁻ − W ⁺| < W ⁰, and passes through at least two distinct data points. Combinatorically, a hypersphere is blocked if and only if it passes through data points in general position, in the sense that no other hypersphere passes through the same data points. A hypersphere is a halving hypersphere if and only if it is blocked, contains exactly k data points inside, confines exactly ℓ data points outside, and |k − ℓ| ≤ 1. In the plane, the present results also show that if a median circle is not a halving circle, then moving its center along a median between two data points on it until it passes through the next data point yields a halving circle. Relative to the center, if the direction cosines of the external and internal data points have the same mean and variance, then the median circle must be blocked, and stays so under sufficiently small perturbations of the data. Moreover, for every set of four points, at least one unweighted median circle is blocked. These results lend credence to a variant of a method used by archaeologists, and explain some findings from operations research.     

Genetic algorithms: Foundations and applications

Genetic algorithms are defined. Attention is directed to why they work: schemas and building blocks, implicit parallelism, and exponentially biased sampling of the better schema. Why they fail and how undesirable behavior can be overcome is discussed. Current genetic algorithm practice is summarized. Five successful applications are illustrated: image registration, AEGIS surveillance, network configuration, prisoner's dilemma, and gas pipeline control. Three classes of problems for which genetic algorithms are ill suited are illustrated: ordering problems, smooth optimization problems, and totally indecomposable problems.     

Fixed interval scheduling: Models,applications, computational complexity and algorithms

The defining characteristic of fixed interval scheduling problems is that each job has a finite number of fixed processing intervals. A job can be processed only in one of its intervals on one of the available machines, or is not processed at all. A decision has to be made about a subset of the jobs to be processed and their assignment to the processing intervals such that the intervals on the same machine do not intersect. These problems arise naturally in different real-life operations planning situations, including the assignment of transports to loading/unloading terminals, work planning for personnel, computer wiring, bandwidth allocation of communication channels, printed circuit board manufacturing, gene identification and examining computer memory structures. We present a general formulation of the interval scheduling problem, show its relations to cognate problems in graph theory, and survey existing models, results on computational complexity and solution algorithms.     

Approximation algorithms for multiple terminal, Hamiltonian path problems

This article presents a new 2-approximation algorithm for a multiple depot, multiple terminal, Hamiltonian path problem when the costs satisfy the triangle inequality. For the case where all the salesmen start from the same depot, we present another algorithm with an approximation ratio of \frac53{\frac{5}{3}}. These results generalize the approximation algorithms currently available for the single depot, single terminal Hamiltonian path problem.     

Multiple UAVs path planning algorithms: a comparative study

Unmanned aerial vehicles (UAVs) are used in team for detecting targets and keeping them in its sensor range. There are various algorithms available for searching and monitoring targets. The complexity of the search algorithm increases if the number of nodes is increased. This paper focuses on multi UAVs path planning and Path Finding algorithms. Number of Path Finding and Search algorithms was applied to various environments, and their performance compared. The number of searches and also the computation time increases as the number of nodes increases. The various algorithms studied are Dijkstra’s algorithm, Bellman Ford’s algorithm, Floyd-Warshall’s algorithm and the AStar algorithm. These search algorithms were compared. The results show that the AStar algorithm performed better than the other search algorithms. These path finding algorithms were compared so that a path for communication can be established and monitored.     

Markovian trees: properties and algorithms

In this paper we introduce a structure called the Markovian tree (MT). We define the MT and explore its alternative representation as a continuous-time Markovian Multitype Branching Process. We then develop two algorithms, the Depth and Order algorithms to determine the probability of eventual extinction of the MT process. We show that both of these algorithms have very natural physically intuitive interpretations and are analogues of the Neuts and U algorithms in Matrix-analytic Methods. Furthermore, we show that a special case of the Depth algorithm sheds new light on the interpretation of the sample paths of the Neuts algorithm.     

The Dial-a-Ride Problem (DARP): Variants,modeling issues and algorithms

The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for n users who specify pick-up and drop-off requests between origins and destinations. The aim is to plan a set of m minimum cost vehicle routes capable of accommodating as many users as possible, under a set of constraints. The most common example arises in door-to-door transportation for elderly or disabled people. The purpose of this article is to review the scientific literature on the DARP. The main features of the problem are described and classified and some modeling issues are discussed. A summary of the most important algorithms is provided.AMS classification: 90B06, 90C27, 90C59     

Improved algorithms for path partition and related problems

We study the L_∞ path partition problem: given a path of n weighted vertices and an integer k, remove k−1 edges from the path so that the maximum absolute deviation of the weights of the resulting k sub-paths from their mean is minimized. Previously, the best algorithm solves this problem in O(nklogk) time. We present an O(nk) time algorithm. We also give improved solutions for two related problems: the L_d path partition problem and the web proxies placement problem.     

Cycle detection algorithms and their applications

This paper considers several cycle detection algorithms. Proofs of their correctness are given, bounds for complexity are obtained, some number theory applications like the factorization of integers and the discrete log problem are examined.     

Vertex packings: Structural properties and algorithms

We consider a binary integer programming formulation (VP) for the weighted vertex packing problem in a simple graph. A sufficient “local” optimality condition for (VP) is given and this result is used to derive relations between (VP) and the linear program (VLP) obtained by deleting the integrality restrictions in (VP). Our most striking result is that those variables which assume binary values in an optimum (VLP) solution retain the same values in an optimum (VP) solution. This result is of interest because variables are (0, 1/2, 1). valued in basic feasible solutions to (VLP) and (VLP) can be solved by a “good” algorithm. This relationship and other optimality conditions are incorporated into an implicit enumeration algorithm for solving (VP). Some computational experience is reported.     

On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling

Recently, Freund and Nachtigal proposed the quasi-minimal residual algorithm (QMR) for solving general nonsingular non-Hermitian linear systems. The method is based on the Lanczos process, and thus it involves matrix—vector products with both the coefficient matrix of the linear system and its transpose. Freund developed a variant of QMR, the transpose-free QMR algorithm (TFQMR), that only requires products with the coefficient matrix. In this paper, the use of QMR and TFQMR for solving singular systems is explored. First, a convergence result for the general class of Krylov-subspace methods applied to singular systems is presented. Then, it is shown that QMR and TFQMR both converge for consistent singular linear systems with coefficient matrices of index 1. Singular systems of this type arise in Markov chain modeling. For this particular application, numerical experiments are reported.     

Interior path following primal-dual algorithms. part I: Linear programming

We describe a primal-dual interior point algorithm for linear programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea.