Restructuring risk in credit default swaps: An empirical analysis

This paper estimates the price for restructuring risk in the US corporate bond market during 1999–2005. Comparing quotes from default swap (CDS) contracts with a restructuring event and without, we find that the average premium for restructuring risk represents 6%–8% of the swap rate without restructuring. We show that the restructuring premium depends on firm-specific balance-sheet and macroeconomic variables. And, when default swap rates without a restructuring event increase, the increase in restructuring premia is higher for low-credit-quality firms than for high-credit-quality firms. We propose a reduced-form arbitrage-free model for pricing default swaps that explicitly incorporates the distinction between restructuring and default events. A case study illustrating the model’s implementation is provided.     

国企重组中的战略重组与整合机制研究——以中国海洋航空集团公司为例

国有企业在我国国民经济发展中占有重要地位,国有企业重组是解决国有企业面临的诸多问题的重要方式,而战略重组与整合是国有企业重组中的重要内容。本文首先提出了国有企业重组中的战略重组与整合机制,然后以中国海洋航空集团公司的成功重组为案例,探讨并总结了其战略重组的成功经验和做法,这能为其它国有企业重组提供重要参考,还有利于丰富国有企业重组的相关理论。     

Two-Person Second-Order Games,Part 2: Restructuring Operations to Reach a Win-Win Profile

In Part 1 of the paper, using habitual domains theory and finite Markov chain theory, we have introduced a new model for describing the evolution of the states of mind of players over time, the two-person second-order game. The concepts of focal mind profile as well as the solution concept of win-win mind profile have been introduced as solution concepts for these games. In Part 2 of the paper, we address the problem of restructuring a game where the focal profile (1,1) is not reachable or is not a win-win profile into a game where the profile (1,1) is a reachable win-win profile. Precisely, under some reasonable assumptions, we derive the possibility theorem that it is always possible to reach a win-win mind profile in a two-person second-order game. Moreover, we provide practical operations for restructuring games for reaching a win-win profile. This research was partially supported by the National Science Council, Taiwan, NSC96-2416-H009-013.     

Restructuring ordered binary trees

We consider the problem of restructuring an ordered binary tree T, preserving the in-order sequence of its nodes, so as to reduce its height to some target value h. Such a restructuring necessarily involves the downward displacement of some of the nodes of T. Our results, focusing both on the maximum displacement over all nodes and on the maximum displacement over leaves only, provide (i) an explicit tradeoff between the worst-case displacement and the height restriction (including a family of trees that exhibit the worst-case displacements) and (ii) efficient algorithms to achieve height-restricted restructuring while minimizing the maximum node displacement.     

An NC Parallel Algorithm for Edge-Coloring Series–Parallel Multigraphs

Many combinatorial problems can be efficiently solved in parallel for series–parallel multigraphs. The edge-coloring problem is one of a few combinatorial problems for which no NC parallel algorithm has been obtained for series–parallel multigraphs. This paper gives an NC parallel algorithm for the problem on series–parallel multigraphsG. It takesO(log n) time withO(Δn/log n) processors, wherenis the number of vertices and Δ is the maximum degree ofG.     

Approximating Huffman codes in parallel

In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work. Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) with n/logn processors, if the elements are sorted.     

Parallel characteristic finite element method for time‐dependent convection–diffusion problem

Based on the overlapping‐domain decomposition and parallel subspace correction method, a new parallel algorithm is established for solving time‐dependent convection–diffusion problem with characteristic finite element scheme. The algorithm is fully parallel. We analyze the convergence of this algorithm, and study the dependence of the convergent rate on the spacial mesh size, time increment, iteration times and sub‐domains overlapping degree. Both theoretical analysis and numerical results suggest that only one or two iterations are needed to reach to optimal accuracy at each time step. Copyright © 2010 John Wiley & Sons, Ltd.     

Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation

The Dirichlet-Neumann and Neumann-Neumann waveform relaxation methods are nonoverlapping spatial domain decomposition methods to solve evolution problems, while the parareal algorithm is in time parallel fashion. Based on the combinations of these space and time parallel strategies, we present and analyze two parareal algorithms based on the Dirichlet-Neumann and the Neumann-Neumann waveform relaxation method for the heat equation by choosing Dirichlet-Neumann/Neumann-Neumann waveform relaxation as two new kinds of fine propagators instead of the classical fine propagator. Both new proposed algorithms could be viewed as a space-time parallel algorithm, which increases the parallelism both in space and in time. We derive for the heat equation the convergence results for both algorithms in one spatial dimension. We also illustrate our theoretical results with numerical experiments finally.

     

On parallel hashing and integer sorting

The problem of sorting n integers from a restricted range [1…m], where m is a superpolynomial in n, is considered. An o(n log n) randomized algorithm is given. Our algorithm takes O(n log log m) expected time and O(n) space. (Thus, for m = n^polylog(n) we have an O(n log log n) algorithm.) The algorithm is parallelizable. The resulting parallel algorithm achieves optimal speedup. Some features of the algorithm make us believe that it is relevant for practical applications. A result of independent interest is a parallel hashing technique. The expected construction time is logarithmic using an optimal number of processors, and searching for a value takes O(1) time in the worst case. This technique enables drastic reduction of space requirements for the price of using randomness. Applicability of the technique is demonstrated for the parallel sorting algorithm and for some parallel string matching algorithms. The parallel sorting algorithm is designed for a strong and nonstandard model of parallel computation. Efficient simulations of the strong model on a CRCW PRAM are introduced. One of the simulations even achieves optimal speedup. This is probably the first optimal speedup simulation of a certain kind.     

On multistage Stochastic Integer Programming for incorporating logical constraints in asset and liability management under uncertainty

We present a model for optimizing a mean-risk function of the terminal wealth for a fixed income asset portfolio restructuring with uncertainty in the interest rate path and the liabilities along a given time horizon. Some logical constraints are considered to be satisfied by the assets portfolio. Uncertainty is represented by a scenario tree and is dealt with by a multistage stochastic mixed 0-1 model with complete recourse. The problem is modelled as a splitting variable representation of the Deterministic Equivalent Model for the stochastic model, where the 0-1 variables and the continuous variables appear at any stage. A Branch-and-Fix Coordination approach for the multistage 0–1 program solving is proposed. Some computational experience is reported.      

Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.     

A parareal in time procedure for the control of partial differential equationsUne technique de contrôle d'équations aux dérivées partielles en temps pararéel

We have proposed in a previous note a time discretization for partial differential evolution equation that allows for parallel implementations. This scheme is here reinterpreted as a preconditioning procedure on an algebraic setting of the time discretization. This allows for extending the parallel methodology to the problem of optimal control for partial differential equations. We report a first numerical implementation that reveals a large interest. To cite this article: Y. Maday, G. Turinici, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 387–392.     

Due-date assignment on uniform machines

The classical weighted minsum scheduling and due-date assignment problem (with earliness, tardiness and due-date costs) was shown to be polynomially solvable on a single machine, more than two decades ago. Later, it was shown to have a polynomial time solution in the case of identical processing time jobs and parallel identical machines. We extend the latter setting to parallel uniform machines. We show that the two-machine case is solved in constant time. Furthermore, the problem remains polynomially solvable for a given (fixed) number of machines.     

Parallel Metaheuristics for Workforce Planning

Workforce planning is an important activity that enables organizations to determine the workforce needed for continued success. A workforce planning problem is a very complex task requiring modern techniques to be solved adequately. In this work, we describe the development of three parallel metaheuristic methods, a parallel genetic algorithm, a parallel scatter search, and a parallel hybrid genetic algorithm, which can find high-quality solutions to 20 different problem instances. Our experiments show that parallel versions do not only allow to reduce the execution time but they also improve the solution quality.      

A parallel algorithm for the maximal path problem

In this paper we present anO (log⁵ n) time parallel algorithm for constructing a Maximal Path in an undirected graph. We also give anO (log^1/2+ε) time parallel algorithm for constructing a depth first search tree in an undirected graph. This work was supported in part by an IBM Faculty Development Award, an NSF Graduate Fellowship, and NSF grant DCR-8351757.     

An analytical formula for variance of output from a series-parallel production system with no interstation buffers and time-dependent failures

This paper presents a method to determine the mean and the variance of the amount of materials produced in a fixed time interval by a continuous materials flow production system with N stations in series and M stations in parallel and no interstation buffers. Unreliable stations with exponential failure and repair times, time dependent failures, and deterministic processing times are considered. Closed-form expressions for the asymptotic mean and variance of the amount of materials produced per unit time are given for series, parallel, and series-parallel production systems with identical stations. It is shown that the distribution of the amount of materials produced in a fixed time is asymptotically normal. By using this property, effects of variability on the due-date performance are investigated by considering the probability of meeting a customer order on time. Numerical experiments that explore some relationships among performance measures and production system parameters are also presented.     

Parallel Synchronous and Asynchronous Space-Decomposition Algorithms for Large-Scale Minimization Problems

Three parallel space-decomposition minimization (PSDM) algorithms, based on the parallel variable transformation (PVT) and the parallel gradient distribution (PGD) algorithms (O.L. Mangasarian, SIMA Journal on Control and Optimization, vol. 33, no. 6, pp. 1916–1925.), are presented for solving convex or nonconvex unconstrained minimization problems. The PSDM algorithms decompose the variable space into subspaces and distribute these decomposed subproblems among parallel processors. It is shown that if all decomposed subproblems are uncoupled of each other, they can be solved independently. Otherwise, the parallel algorithms presented in this paper can be used. Numerical experiments show that these parallel algorithms can save processor time, particularly for medium and large-scale problems. Up to six parallel processors are connected by Ethernet networks to solve four large-scale minimization problems. The results are compared with those obtained by using sequential algorithms run on a single processor. An application of the PSDM algorithms to the training of multilayer Adaptive Linear Neurons (Madaline) and a new parallel architecture for such parallel training are also presented.     

On stability of steady-state plane–parallel shearing flows in a homogeneous in density ideal incompressible fluid

A problem on linear stability of stationary plane–parallel shearing flows in a homogeneous in density inviscid incompressible fluid between two immovable impermeable solid parallel infinite plates is studied. With the use of the direct Lyapunov method it is shown that all sufficient conditions (by Rayleigh, Fjørtoft, Arnol’d) known to this moment for stability of these flows with respect to small plane perturbations are the necessary ones as well. An a priori lower estimate is constructed; the estimate displays exponential in time growth of the considered perturbations if these conditions are not affected. An analytical example of steady-state plane–parallel shearing flows and superimposed small plane perturbations growing in time in accordance with the constructed estimate is given.     

The average performance of a parallel stable marriage algorithm

In this paper, Tseng and Lee's parallel algorithm to solve the stable marriage prolem is analyzed. It is shown that the average number of parallel proposals of the algorithm is of ordern by usingn processors on a CREW PRAM, where each parallel proposal requiresO(loglog(n) time on CREW PRAM by applying the parallel selection algorithms of Valiant or Shiloach and Vishkin. Therefore, our parallel algorithm requiresO(nloglog(n)) time. The speed-up achieved is log(n)/loglog(n) since the average number of proposals required by applying McVitie and Wilson's algorithm to solve the stable marriage problem isO(nlog(n)).     

Parallel comparison algorithms for approximation problems

Suppose we haven elements from a totally ordered domain, and we are allowed to performp parallel comparisons in each time unit (=round). In this paper we determine, up to a constant factor, the time complexity of several approximation problems in the common parallel comparison tree model of Valiant, for all admissible values ofn, p and , where is an accuracy parameter determining the quality of the required approximation. The problems considered include the approximate maximum problem, approximate sorting and approximate merging. Our results imply as special cases, all the known results about the time complexity for parallel sorting, parallel merging and parallel selection of the maximum (in the comparison model), up to a constant factor. We mention one very special but representative result concerning the approximate maximum problem; suppose we wish to find, among the givenn elements, one which belongs to the biggestn/2, where in each round we are allowed to askn binary comparisons. We show that log^* n+O(1) rounds are both necessary and sufficient in the best algorithm for this problem.Research supported in part by Allon Fellowship, by a Bat Sheva de Rothschild grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.