A stochastic approximation algorithm with step size adaptation

Plakhov, A.Y.; Cruz, P., (2004) 'A stochastic approximation algorithm with step size adaptation', Journal of Mathematical Science 120(1) pp.964-973 RAE2008

On the Performance of Polynomial-time CLIQUE Approximation Algorithms on Very Large Graphs

The performance of a randomized version of the subgraph-exclusion algorithm (called Ramsey) for CLIQUE by Boppana and Halldorsson is studied on very large graphs. We compare the performance of this algorithm with the performance of two common heuristic algorithms, the greedy heuristic and a version of simulated annealing. These algorithms are tested on graphs with up to 10,000 vertices on a workstation and graphs as large as 70,000 vertices on a Connection Machine. Our implementations establish the ability to run clique approximation algorithms on very large graphs. We test our implementations on a variety of different graphs. Our conclusions indicate that on randomly generated graphs minor changes to the distribution can cause dramatic changes in the performance of the heuristic algorithms. The Ramsey algorithm, while not as good as the others for the most common distributions, seems more robust and provides a more even overall performance. In general, and especially on deterministically generated graphs, a combination of simulated annealing with either the Ramsey algorithm or the greedy heuristic seems to perform best. This combined algorithm works particularly well on large Keller and Hamming graphs and has a competitive overall performance on the DIMACS benchmark graphs.

Recognition of Human Action Using Moment-Based Feature

The performance of different classification approaches is evaluated using a view-based approach for motion representation. The view-based approach uses computer vision and image processing techniques to register and process the video sequence. Two motion representations called Motion Energy Images and Motion History Image are then constructed. These representations collapse the temporal component in a way that no explicit temporal analysis or sequence matching is needed. Statistical descriptions are then computed using moment-based features and dimensionality reduction techniques. For these tests, we used 7 Hu moments, which are invariant to scale and translation. Principal Components Analysis is used to reduce the dimensionality of this representation. The system is trained using different subjects performing a set of examples of every action to be recognized. Given these samples, K-nearest neighbor, Gaussian, and Gaussian mixture classifiers are used to recognize new actions. Experiments are conducted using instances of eight human actions (i.e., eight classes) performed by seven different subjects. Comparisons in the performance among these classifiers under different conditions are analyzed and reported. Our main goals are to test this dimensionality-reduced representation of actions, and more importantly to use this representation to compare the advantages of different classification approaches in this recognition task.

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

The numerical simulation of enclosure fires using a Cfd fire field model coupled with a pyrolysis based solid fuel combustion submodel—a first approximation

In this paper, we present some early work concerned with the development of a simple solid fuel combustion model incorporated within a Computational Fluid Dynamics (CFD) framework. The model is intended for use in engineering applications of fire field modeling and represents an extension of this technique to situations involving the combustion of solid cellulosic fuels. A simple solid fuel combustion model consisting of a thermal pyrolysis model, a six flux radiation model and an eddy-dissipation model for gaseous combustion have been developed and implemented within the CFD code CFDS-FLOW3D. The model is briefly described and demonstrated through two applications involving fire spread in a compartment with a plywood lined ceiling. The two scenarios considered involve a fire in an open and closed compartment. The model is shown to be able to qualitatively predict behaviors similar to "flashover"—in the case of the open room—and "backdraft"— in the case of the initially closed room.

Moment decay rates of solutions of stochastic differential equations

The objective of this paper is to investigate the p-ίh moment asymptotic stability decay rates for certain finite-dimensional Itό stochastic differential equations. Motivated by some practical examples, the point of our analysis is a special consideration of general decay speeds, which contain as a special case the usual exponential or polynomial type one, to meet various situations. Sufficient conditions for stochastic differential equations (with variable delays or not) are obtained to ensure their asymptotic properties. Several examples are studied to illustrate our theory.

Approximation Algorithms for a Symmetric Quadratic Knapsack Problem and its Scheduling Applications

We consider a knapsack problem to minimize a symmetric quadratic function. We demonstrate that this symmetric quadratic knapsack problem is relevant to two problems of single machine scheduling: the problem of minimizing the weighted sum of the completion times with a single machine non-availability interval under the non-resumable scenario; and the problem of minimizing the total weighted earliness and tardiness with respect to a common small due date. We develop a polynomial-time approximation algorithm that delivers a constant worst-case performance ratio for a special form of the symmetric quadratic knapsack problem. We adapt that algorithm to our scheduling problems and achieve a better performance. For the problems under consideration no fixed-ratio approximation algorithms have been previously known.

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

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.

Approximation results for flow shop scheduling problems with machine availability constraints

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

Postcolonial futures: postcolonial literature and the Obama moment

In an analysis of President Obama's Acceptance Speech, this article argues that postcolonial theory is now being re-formulated for a global, transnational sensibility.

Postcolonial futures: postcolonial literature and the Obama moment

Since the late 1970s the western academy has encouraged the development of postcolonial literary theory and the formulation of a postcolonial literary canon existing outside the prescriptive narratives of the ‘mother’ country and empire. Having lost faith in the binary oppositions underpinning such narratives, we turned to alternative fictions that contested the construction of the ‘other’, the world divided between the ‘West and the Rest’. The publication of Edward Said’s Orientalism in 1978 marked the beginning of the discipline now known as postcolonial studies with its new ways of understanding ‘the west’s’ relationship with ‘the east’ and, by extension, all the former colonies of empire. Despite these radical origins, however, postcolonialism’s more recent emphasis on the psychological and its affirmation of the hybrid text and self has, for many, served to obscure real economic social realities that have very little to do with the magical or wondrous textual expression of a postcolonial identity. This paper considers problems associated with defining the postcolonial and proposes that, in a literary context, we broaden its meaning to include texts traditionally outside the category of postcolonial literature. To extend the meaning of postcolonial is timely as we are now witnessing its relocation from ‘margin’ to ‘centre’ with the election of Barack Obama. This moment may be seen as a disruption of conventional understandings of what constitutes postcolonial literature, essentially as oppositional discourse that could only define itself as peripheral to, or ‘post’, metropolitan and economic concerns. [From the Author]