Minimizing the object dimensions in circle and sphere packing problems

Given a fixed set of identical or different-sized circular items, the problem we deal with consists on finding the smallest object within which the items can be packed. Circular, triangular, squared, rectangular and also strip objects are considered. Moreover, 2D and 3D problems are treated. Twice-differentiable models for all these problems are presented. A strategy to reduce the complexity of evaluating the models is employed and, as a consequence, instances with a large number of items can be considered. Numerical experiments show the flexibility and reliability of the new unified approach. (C) 2007 Elsevier Ltd. All rights reserved.

Mentors, students, and the undergraduate medical course: a virtuous circle

BACKGROUND: Mentoring Programs have been developed in several medical schools, but few studies have investigated the mentors'perspective. PURPOSES: To explore mentors'perceptions regarding their experience. METHODS: Mentors at a medical school were invited to participate in an in-depth interview including questions on satisfaction, difficulties, and perception of changes resulting from the program. RESULTS: Mentors' satisfaction and difficulties are strongly associated with students'involvement in the activity. Mentors believe changes observed in students were more related to life issues; for some mentors, there is no recognition or awareness of the program. However, most of the mentors acknowledged important changes in relation to themselves: as teachers, faculty members, and individuals. CONCLUSION: Attendance is crucial for both the mentoring relationship and strengthening of the program. Students involved in the activity motivate mentors in teaching and curriculum development, thereby creating a virtuous circle and benefiting undergraduate medical education as a whole.

Coordination dynamics and attentional costs of continuous and discontinuous bimanual circle drawing movements

It has been suggested that the temporal control of rhythmic unimianual movements is different between tasks requiring continuous (e.g., circle drawing) and discontinuous movements (e.g., finger tapping). Specifically, for continuous movements temporal regularities are ail emergent property, whereas for tasks that involve discontinuities timing is ail explicit part of the action goal. The present experiment further investigated the control of continuous and discontinuous movements by comparing the coordination dynamics and attentional demands of bimanual continuous circle drawing with bimanual intermittent circle drawing. The intermittent task required participants to insert a 400 ms pause between each cycle while circling. Using dual-task methodology, 15 right-handed participants performed the two circle drawing tasks, while vocally responding to randomly presented auditory probes. The circle drawing tasks were performed in symmetrical and asymmetrical coordination modes and at movement frequencies of 1 Hz and 1.7 Hz. Intermittent circle drawing exhibited superior spatial and temporal accuracy and stability than continuous circle drawing supporting the hypothesis that the two tasks have different underlying control processes. In terms of attentional cost, probe RT was significantly slower during the intermittent circle drawing task than the continuous circle drawing task across both coordination modes and movement frequencies. Of interest was the finding that in the intermittent circling task reaction time (RT) to probes presented during the pause between cycles did not differ from the RT to probes occurring during the circling movement. The differences in attentional demands between the intermittent and continuous circle drawing tasks may reflect the operation of explicit event timing and implicit emergent timing processes, respectively. (C) 2008 Elsevier B.V. All rights reserved.

Performance evaluation of packing materials in the removal of hydrogen sulphide in gas-phase biofilters: Polyurethane foam, sugarcane bagasse, and coconut fibre

The main objective of this work was to investigate three packing materials (polyurethane foam, sugar-cane bagasse, and coconut fibre) for biofiltration of a gaseous mixture containing hydrogen sulphide (H(2)S). Mixed cultures were obtained from two sources, aerated submerged biofilters and activated sludge, and were utilised as inoculums. Biofilters reached 100% removal efficiency after two clays of operation. The empty bed residence time was 495 for each of the biofilters. The reactors were operated simultaneously, and the inlet concentrations of H(2)S varied between 184 and 644 ppmv during the long-term continuous operation of the biofilters (100 clays). Average removal efficiencies remained above 99.3%, taking into consideration the entire period of operation. Average elimination capacities reached by the biofilters packed with polyurethane foam, coconut fibre, and sugarcane bagasse were in the range of 17.8-66.6; 18.9-68.8, and 18.7-72.9g m(-3) h(-1), respectively. Finally, we concluded that the packing materials tested in this work are appropriate for the long-term biofiltration of hydrogen sulphide. (C) 2010 Elsevier B.V. All rights reserved.

Replacement of Trays by Packing To Increase the Absorption Capacity of Acetone during Cellulose Acetate Spinning

All textile uses of cellulose acetate involve acetone recovery, which, because of safety issues, results in large installations, in order to work with dilute streams. This compromises the efficiency of all of the involved unit operations, in this case, acetone absorption in cold water, acetone distillation, and water chilling, making them more expensive. The present article proposes the improvement of the absorption of acetone in water, traditionally performed with sieve trays, by using structured packing instead. The advantageous implementation was enabled through the utilization of a calculation methodology based on concepts of thermodynamic equilibrium of the binary acetone/water system and empirical relations that allow the evaluation of the hydrodynamics of the proposed modification.

Open cluster survival within the solar circle: Teutsch 145 and Teutsch 146 star

Teutsch 145 and Teutsch 146 are shown to be open clusters (OCs) orbiting well inside the solar circle, a region where several dynamical processes combine to disrupt most OCs on a time-scale of a few 108 yr. BVI photometry from the GALILEO telescope is used to investigate the nature and derive the fundamental and structural parameters of the optically faint and poorly known OCs Teutsch 145 and 146. These parameters are computed by means of field-star-decontaminated colour-magnitude diagrams and stellar radial density profiles (RDPs). Cluster mass estimates are made based on the intrinsic mass functions (MFs). We derive the ages 200+100(-50) and 400 +/- 100 Myr, and the distances from the Sun d(circle dot) = 2.7 +/- 0.3 and 3.8 +/- 0.2 kpc, respectively, for Teutsch 145 and 146. Their integrated apparent and absolute magnitudes are m(V) approximate to 12.4 and 13.3 and M(V) approximate to -5.6 and -5.3. The MFs (detected for stars with m greater than or similar to 1 M(circle dot)) have slopes similar to Salpeter`s initial mass function. Extrapolated to the H-burning limit, the MFs would produce total stellar masses of similar to 1400 M(circle dot), typical of relatively massive OCs. Both OCs are located deep into the inner Galaxy and close to the Crux-Scutum arm. Since cluster-disruption processes are important, their primordial masses must have been higher than the present-day values. The conspicuous stellar density excess observed in the innermost bin of both RDPs might reflect the dynamical effects induced by a few 108 yr of external tidal stress.

TRANSITIVE CIRCLE EXCHANGE TRANSFORMATIONS WITH FLIPS

We study the existence of transit we exchange transformations with flips defined on the unit circle S(1). We provide a complete answer to the question of whether there exists a transitive exchange transformation of S(1) defined on a subintervals and having f flips.

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

New and improved results for packing identical unitary radius circles within triangles, rectangles and strips

The focus of study in this paper is the class of packing problems. More specifically, it deals with the placement of a set of N circular items of unitary radius inside an object with the aim of minimizing its dimensions. Differently shaped containers are considered, namely circles, squares, rectangles, strips and triangles. By means of the resolution of non-linear equations systems through the Newton-Raphson method, the herein presented algorithm succeeds in improving the accuracy of previous results attained by continuous optimization approaches up to numerical machine precision. The computer implementation and the data sets are available at http://www.ime.usp.br/similar to egbirgin/packing/. (C) 2009 Elsevier Ltd, All rights reserved.

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50 000 instances). It is also effective for solving the instances of problem set Cover III (almost 100 000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes. Journal of the Operational Research Society (2010) 61, 306-320. doi: 10.1057/jors.2008.141 Published online 4 February 2009

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Decay of geometry for Fibonacci critical covering maps of the circle

We study the growth of Df `` (f(c)) when f is a Fibonacci critical covering map of the circle with negative Schwarzian derivative, degree d >= 2 and critical point c of order l > 1. As an application we prove that f exhibits exponential decay of geometry if and only if l <= 2, and in this case it has an absolutely continuous invariant probability measure, although not satisfying the so-called Collet-Eckmann condition. (C) 2009 Elsevier Masson SAS. All rights reserved.