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.

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.

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.

Packing a trunk : a physically based approach with full motional freedom

Geometric packing problems may be formulated mathematically as constrained optimization problems. But finding a good solution is a challenging task. The more complicated the geometry of the container or the objects to be packed, the more complex the non-penetration constraints become. In this work we propose the use of a physics engine that simulates a system of colliding rigid bodies. It is a tool to resolve interpenetration conflicts and to optimize configurations locally. We develop an efficient and easy-to-implement physics engine that is specialized for collision detection and contact handling. In succession of the development of this engine a number of novel algorithms for distance calculation and intersection volume were designed and imple- mented, which are presented in this work. They are highly specialized to pro- vide fast responses for cuboids and triangles as input geometry whereas the concepts they are based on can easily be extended to other convex shapes. Especially noteworthy in this context is our ε-distance algorithm - a novel application that is not only very robust and fast but also compact in its im- plementation. Several state-of-the-art third party implementations are being presented and we show that our implementations beat them in runtime and robustness. The packing algorithm that lies on top of the physics engine is a Monte Carlo based approach implemented for packing cuboids into a container described by a triangle soup. We give an implementation for the SAE J1100 variant of the trunk packing problem. We compare this implementation to several established approaches and we show that it gives better results in faster time than these existing implementations.

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.

Packing complete multipartite graphs with 4-cycles

In this paper we completely solve the problem of finding a maximum packing of any complete multipartite graph with edge-disjoint 4-cycles, and the minimum leaves are explicitly given.

Hamiltonian mappings and circle packing phase spaces.

We introduce three area preserving maps with phase space structures which resemble circle packings. Each mapping is derived from a kicked Hamiltonian system with one of the three different phase space geometries (planar, hyperbolic or spherical) and exhibits an infinite number of coexisting stable periodic orbits which appear to ‘pack’ the phase space with circular resonances.

A physical packing sequence algorithm for the container loading problem with static mechanical equilibrium conditions

The container loading problem (CLP) is a combinatorial optimization problem for the spatial arrangement of cargo inside containers so as to maximize the usage of space. The algorithms for this problem are of limited practical applicability if real-world constraints are not considered, one of the most important of which is deemed to be stability. This paper addresses static stability, as opposed to dynamic stability, looking at the stability of the cargo during container loading. This paper proposes two algorithms. The first is a static stability algorithm based on static mechanical equilibrium conditions that can be used as a stability evaluation function embedded in CLP algorithms (e.g. constructive heuristics, metaheuristics). The second proposed algorithm is a physical packing sequence algorithm that, given a container loading arrangement, generates the actual sequence by which each box is placed inside the container, considering static stability and loading operation efficiency constraints.

Effects of grain shape on packing and dilatancy of sheared granular materials

Aus: Soft matter, Vol. 10.2014, H. 28, S. 5157 - 5167

Are you packing a healthy lunch? (English and Irish)

This booklet is designed toimprove pupils' nutrition and implement healthier eating and drinking practices. It containspractical tips for parents, carers and children on how to pack an appetising, healthy lunchbox.