A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

A distributed algorithm for European options with nonlinear volatility

A distributed algorithm is developed to solve nonlinear Black-Scholes equations in the hedging of portfolios. The algorithm is based on an approximate inverse Laplace transform and is particularly suitable for problems that do not require detailed knowledge of each intermediate time steps.

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables

An approximation algorithm for the two-machine flow shop with a single transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

An algorithm for total variation inpainting based on nonlinear multi-grid methods

Image inpainting refers to restoring a damaged image with missing information. The total variation (TV) inpainting model is one such method that simultaneously fills in the regions with available information from their surroundings and eliminates noises. The method works well with small narrow inpainting domains. However there remains an urgent need to develop fast iterative solvers, as the underlying problem sizes are large. In addition one needs to tackle the imbalance of results between inpainting and denoising. When the inpainting regions are thick and large, the procedure of inpainting works quite slowly and usually requires a significant number of iterations and leads inevitably to oversmoothing in the outside of the inpainting domain. To overcome these difficulties, we propose a solution for TV inpainting method based on the nonlinear multi-grid algorithm.

Knowledge networks change during radical and incremental innovation episodes: a case study on software developmen

The role intra-organizational knowledge exchanges play in innovation processes has been widely acknowledged in the organizational literature. This paper contributes to the understanding of which specific configurations knowledge networks assume during different phases of radical and incremental innovation processes. The case study we selected is a FLOSS (Free/Libre Open Source Software) community consisting of 233 developers committed to the development of a web browser application since November 2002. By harvesting the mailing list, official blog and code repository of a FLOSS community, we investigate the patterns of knowledge exchange and individual contributions of its developers. We measure structural cohesion and compare global and local network properties at different points in time. Preliminary results show that phases of radical and incremental innovation are associated with specific configurations of the knowledge network as a whole as well as with different network positions of the core developers of the software.

The effects of cadence and power output upon physiological and biomechanical responses to incremental arm-crank ergometry

The aim of this study was to examine the effects of cadence and power output on physiological and biomechanical responses to incremental arm-crank ergometry (ACE). Ten male subjects (mean +/- SD age, 30.4 +/-5.4 y; height, 1.78 +/-0.07 m; mass, 86.1 +/-14.2 kg) undertook 3 incremental ACE protocols to determine peak oxygen uptake (VO2 peak; mean of 3 tests: 3.07 +/- 0.17 L.min-1) at randomly assigned cadences of 50, 70, or 90 r.min-1. Heart rate and expired air were continually monitored. Central (RPE-C) and local (RPE-L) ratings of perceived exertion were recorded at volitional exhaustion. Joint angles and trunk rotation were analysed during each exercise stage. During submaximal power outputs of 50, 70, and 90 W, oxygen consumption (VO2) was lowest for 50 r.min-1 and highest for 90 r.min-1 (p < 0.01). VO2 peak was lowest during 50 r.min-1 (2.79 +/-0.45 L.min-1; p < 0.05) when compared with both 70 r.min-1 and 90 r.min-1 (3.16 +/-0.58, 3.24 +/-0.49 L.min-1, respectively; p > 0.05). The difference between RPE-L and RPE-C at volitional exhaustion was greatest during 50 r.min-1 (2.9 +/- 1.6) when compared with 90 r.min-1 (0.9 +/- 1.9, p < 0.05). At VO2 peak, shoulder range of motion (ROM) and trunk rotation were greater for 50 and 70 r.min-1 when compared with 90 r.min-1 (p < 0.05). During submaximal power outputs, shoulder angle and trunk rotation were greatest at 50 r.min-1 when compared with 90 r.min-1 (p < 0.05). VO2 was inversely related to both trunk rotation and shoulder ROM during submaximal power outputs. The results of this study suggest that the greater forces required at lower cadences to produce a given power output resulted in greater joint angles and range of shoulder and trunk movement. Greater isometric contractions for torso stabilization and increased cost of breathing possibly from respiratory-locomotor coupling may have contributed increased oxygen consumption at higher cadences.