Search

We present a family of scale-free network model consisting of cliques, which is established by a simple recursive algorithm. We investigate the networks both analytically and numerically. The obtained analytical solutions show that the networks follow a power-law degree distribution, with degree exponent continuously tuned between 2 and 3. The exact expression of clustering coefficient is also provided for the networks. Furthermore, the investigation of the average path length reveals that the networks possess small-world feature. Interestingly, we find that a special case of our model can be mapped into the Yule process. [ABSTRACT FROM AUTHOR]

We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419-453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.) [ABSTRACT FROM AUTHOR]

In many optimization problems, one seeks to allocate a limited set of resources to a set of individuals with demands. Thus, such allocations can naturally be viewed as vectors, with one coordinate representing each individual. Motivated by work in network routing and bandwidth assignment, we consider the problem of producing solutions that simultaneously approximate all feasible allocations in a coordinate-wise sense. This is a very strong type of ‘global’ approximation guarantee, and we explore its consequences in a wide range of discrete optimization problems, including facility location, scheduling, and bandwidth assignment in networks. A fundamental issue—one not encountered in the traditional design of approximation algorithms—is that good approximations in this global sense need not exist for every problem instance; there is no a priori reason why there should be an allocation that simultaneously approximates all others. As a result, the existential questions concerning such good allocations lead to a new perspective on a number of fundamental problems in resource allocation, and on the structure of their feasible solutions. [ABSTRACT FROM AUTHOR]

Jackson and Wormald conjecture that if G is a 3-connected n-vertex graph with maximum degree d ≥ 4, then G has a cycle of length Ω(nlogd-1 ²). We show that this conjecture holds when d - 1 is replaced by max{64, 4d + 1}. Our proof implies a cubic algorithm for finding such a cycle. [ABSTRACT FROM AUTHOR]

We develop an iterative method for solving the KKT system of the semi-infinite programming (SIP) problem. At each iteration, we solve the KKT system of a nonlinear programming problem with finite constraints by a semismooth Newton method. The algorithm either terminates at a KKT point of the SIP problem in finitely many iterations or generates an infinite sequence of iterates whose any accumulation point is a KKT point of the problem. We also analyse the convergence rate of the method. Preliminary numerical results are reported. [ABSTRACT FROM AUTHOR]

We propose a new inexact line search rule and analyze the global convergence and convergence rate of related descent methods. The new line search rule is similar to the Armijo line-search rule and contains it as a special case. We can choose a larger stepsize in each line-search procedure and maintain the global convergence of related line-search methods. This idea can make us design new line-search methods in some wider sense. In some special cases, the new descent method can reduce to the Barzilai and Borewein method. Numerical results show that the new line-search methods are efficient for solving unconstrained optimization problems. [ABSTRACT FROM AUTHOR]

Background In many clinical trials, data are collected longitudinally over time. In such studies, missingness, in particular dropout, is an often encountered phenomenon. Methods We discuss commonly used but often problematic methods such as complete case analysis and last observation carried forward and contrast them with broadly valid and easy to implement direct-likelihood methods. We comment on alternatives such as multiple imputation and the expectation-maximization algorithm. Results We apply these methods in particular to data from a study with continuous outcomes. The outcomes are modelled using a general linear mixed-effects model. The bias with CC and LOCF is established in the case study and the advantages of the direct-likelihood approach shown. Conclusions We have established formal but easy to understand arguments for a shift towards a direct-likelihood paradigm when analysing incomplete data from longitudinal clinical trials, necessitating neither imputation nor deletion. [ABSTRACT FROM AUTHOR]

Copyright of Canadian Journal of Chemical Engineering is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Abstract Area openings and closings are morphological filters which efficiently suppress impulse noise from an image, by removing small connected components of level sets. The problem of an objective choice of threshold for the area remains open. Here, a mathematical model for random images will be considered. Under this model, a Poisson approximation for the probability of appearance of any local pattern can be computed. In particular, the probability of observing a component with size larger than k in pure impulse noise has an explicit form. This permits the definition of a statistical test on the significance of connected components, thus providing an explicit formula for the area threshold of the denoising filter, as a function of the impulse noise probability parameter. Finally, using threshold decomposition, a denoising algorithm for grey level images is proposed. [ABSTRACT FROM AUTHOR]

We consider the n-player houseswapping game of Shapley and Scarf (1974), with indifferences in preferences allowed. It is well known that the strict core of such a game may be empty, single valued, or multi valued. We define a condition on such games called segmentability, which means that the set of players can be partitioned into a top trading segmentation. It generalizes Gale's well-known idea of the partition of players into top trading cycles (which is used to find the unique strict core allocation in the model with no indifference). We prove that a game has a nonempty strict core if and only if it is segmentable. We then use this result to devise an O n3 algorithm which takes as input any houseswapping game, and returns either a strict core allocation or a report that the strict core is empty. Finally, we are also able to construct a linear inequality system whose feasible region's extreme points precisely correspond to the allocations of the strict core. This last result parallels the results of Vande Vate (1989) and Rothblum (1992) for the marriage game of Gale and Shapley (1962). [ABSTRACT FROM AUTHOR]

Discusses an algorithm for solving a phase transition problem in a multicomponent system. Consideration of multicomponent solution crystallization on the basis of the example of liquid-phase epitaxy (LPE); Mathematical simulation of the LPE process; Statement of the differential problem; Illustration of the solution algorithm.

A theoretical foundation is presented for modeling and convergence analysis of a class of distributed coevolutionary algorithms applied to optimization problems in which the variables are partitioned among p nodes. An evolutionary algorithm at each of the p nodes performs a local evolutionary search based on its own set of primary variables and the secondary variable set at each node is clamped during this phase. An infrequent intercommunication between the nodes updates the secondary variables at each node. The local search and intercommunication phases alternate, resulting in a cooperative search by the p nodes.

Neighbor games arise from certain matching or sequencing situations in which only some specific pairs of players can obtain a positive gain. As a consequence, the class of neighbor games is the intersection of the class of assignment games (Shapley and Shubik (1972)) and the class of component additive games (Curiel et al. (1994)). We first present some elementary features of neighbor games. After that we provide a polynomially bounded algorithm of order p⊃3 for calculating the leximax solution (cf. Arin and Iñarra (1997)) of neighbor games, where p is the number of players. [ABSTRACT FROM AUTHOR]

Deformation behavior of soft-matrix two-phase alloys has been computed using a continuum mechanics model based on an Isostrain condition, while the stress is distributed by the rule of mixtures. A genetic algorithm (GA) was used to optimize the mechanical modeling parameters such as the resistance and the formability of each phase. The stress–strain curves have been calculated as a function of volume fraction and mechanical properties of phases. The calculated and experimental stress–strain curves are compared and good agreement is found. The resistances increases with the rise of the hard phase volume fraction; this is more important with the presence of the hard phase than with the soft one. A linear law of variation of the phase resistance allows to interpolate and extrapolate the model, a good agreement is found with the evolution of the mechanical behavior. [ABSTRACT FROM AUTHOR]

A three-dimensional dynamic program for the anaysis of large deformations in contact-penetration problems is developed using the finite element Lagrangian method with explicit time integration. By incorporating a tetrahedral element, which allows a single-point integration without a special hourglass control scheme, this program can be more effective to the present problem. The position code algorithm is used to search contact surface. Eroding surfaces are also considered. The defense node algorithm was slightly modified for the calculation of contact forces. A study of obliquity effects on metallic plate perforation and ricochet processes in thin plates impacted by a sphere was conducted. It is well simulated that on separation of two parts of the sphere, the portion still within the crater tends to perforate, while the portion in contact with the plate surface ricochets. This deformation pattern is observed in experiments, especially at high obliquities. A long rod that impacts an oblique steel plate at high impact velocity was also simulated in order to study the dynamics of the rod caused by the three dimensional asymmetric contact. The agreement between simulated and experimental results is quite good. Fracture phenomena occuring at high obliquity deserves further investigations. [ABSTRACT FROM AUTHOR]

A propagating interface can develop corners and discontinuities as it advances. Level set algorithms have been extensively applied for the problems in which the solution has advancing fronts. One of the most popular level set algorithms is the so-called fast marching method (FMM), which requires total O(N log2 N) operations, where N is the number of grid points. The article is concerned with the development of an O(N) level set algorithm called the group marching method (GMM). The new method is based on the narrow band approach as in the FMM. However, it is incorporating a correction-by-iteration strategy to advance a group of grid points at a time, rather than sorting the solution in the narrow band to march forward a single grid point. After selecting a group of grid points appropriately, the GMM advances the group in two iterations for the cost of slightly larger than one iteration. Numerical results are presented to show the efficiency of the method, applied to the eikonal equation in two and three dimensions. [ABSTRACT FROM AUTHOR]

There are many algorithms for the space-time mapping of nested loops. Some of them even make the optimal choices within their framework. We propose a preprocessing phase for algorithms in the polytope model, which extends the model and yields space-time mappings whose schedule is, in some cases, orders of magnitude faster. These are cases in which the dependence graph has small irregularities. The basic idea is to split the index set of the loop nests into parts with a regular dependence structure and apply the existing space-time mapping algorithms to these parts individually. This work is based on a seminal idea in the more limited context of loop parallelization at the code level. We elevate the idea to the model level (our model is the polytope model), which increases its applicability by providing a clearer and wider range of choices at an acceptable analysis cost. Index set splitting is one facet in the effort to extend the power of the polytope model and to enable the generation of competitive target code. [ABSTRACT FROM AUTHOR]

Copyright of Management Science is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Focuses on the ability to mathematically correct motion-blurred images that result from relative motion between the camera and the object. The motion deblurring problem as a linear inverse problem; Application of the ML/EM algorithm; Discussion of certain cases.

A fast and easily implementable approximation algorithm for the problem of finding a minimum makespan in a job shop is presented. The algorithm is based on a taboo search technique with a specific neighborhood definition which employs a critical path and blocks of operations notions. Computational experiments (up to 2,000 operations) show that the algorithm not only finds shorter makespans than the best approximation approaches but also runs in shorter time. It solves the well-known 10 x 10 hard benchmark problem within 30 seconds on a personal computer. [ABSTRACT FROM AUTHOR]

We present a family of variants of the Simplex method, which are based on a Constraint-By-Constraint procedure: the solution to a linear program is obtained by solving a sequence of subproblems with an increasing number of constraints. We discuss several probabilistic models for generating linear programs. In all of them the underlying distribution is assumed to be invariant under changing the signs of rows or columns in the problem data. A weak regularity condition is also assumed. Under these models, for linear programs with d variables and m + d inequality constraints, the expected number of pivots required by these algorithms is bounded by a function of min(m, d) only. In particular this means that, for a fixed number of variables, the expected number of pivots is bounded by a constant when the number of constraints tends to infinity. Since Smale's original model [S1] satisfies our probabilistic assumptions, the same results apply to his model, although not to the particular algorithm he analyzes. We also present some results for models generating only feasible linear programs, and for Bland's pivoting rule. We conclude with a discussion of our probabilistic models, and show why they are inadequate for obtaining meaningful results unless d and m are of the same order of magnitude. [ABSTRACT FROM AUTHOR]

Presents the greedy and heuristic algorithms used in codes and coloring problems. Review of the partitioning methods for constant weight codes and asymmetric codes; Brief discussion of the main heuristic used; Methods that can be applied to further improve the outcomes of the algorithms.

This article focuses on the book "Modelling and Simulation in Air Traffic Management," edited by Lucio Bianco, Paolo Dell'Olmo and Amedeo R. Odoni. It has nine papers, originally presented during a workshop held in Capri in October 1995. It focuses on mathematical models and computational algorithms for air traffic management systems.