We propose a constraint-based approach for the two-dimensional rectangular packing problem with orthogonal orientations. This problem is to arrange a set of rectangles that can be rotated by 90 degrees into a rectangle of minimal size such that no two rectangles overlap. It arises in the placement of electronic devices during the layout of 2.5D System-in-Package integrated electronic systems. Moffitt et al.  solve the packing without orientations with a branch and bound approach and use constraint propagation. We generalize their propagation techniques to allow orientations. Our approach is compared to a mixed-integer program and we provide results that outperform it.
Open cell foams are a promising and versatile class of porous materials. Open metal foams serve as crash absorbers and catalysts, metal and ceramic foams are used for filtering, and open polymer foams are hidden in every-day-life items like mattresses or chairs. Due to their high porosity, classical 2d quantitative analysis can give only very limited information about the microstructure of open foams. On the other hand, micro computed tomography (μCT) yields high quality 3d images of open foams. Thus 3d imaging is the method of choice for open cell foams. In this report we summarise a variety of methods for the analysis of the resulting volume images of open foam structures developed or refined and applied at the Fraunhofer ITWM over a course of nearly ten years: The model based determination of mean characteristics like the mean cell volume or the mean strut thickness demanding only a simple binarisation as well as the image analytic cell reconstruction yielding empirical distributions of cell characteristics.
The problem discussed in this paper is motivated by the new recycling directiveWEEE of the EC. The core of this law is, that each company which sells electrical or electronic equipment in a European country has the obligation to recollect and recycle an amount of returned items which is proportional to its market share. To assign collection stations to companies, in Germany for one product type a territory design approach is planned. However, in contrast to classical territory design, the territories should be geographically as dispersed as possible to avoid that a company, resp. its logistics provider responsible for the recollection, gains a monopoly in some region. First, we identify an appropriate measure for the dispersion of a territory. Afterwards, we present a first mathematical programming model for this new problem as well as a solution method based on the GRASP methodology. Extensive computational results illustrate the suitability of the model and assess the effectiveness of the heuristic.
In this paper we introduce a cooperative game based on the minimum cut tree problem which is also known as multi-terminal maximum flow problem. Minimum cut tree games are shown to be totally balanced and a solution in their core can be obtained in polynomial time. This special core allocation is closely related to the solution of the original graph theoretical problem. We give an example showing that the game is not supermodular in general, however, it is for special cases and for some of those we give an explicit formula for the calculation of the Shapley value.
Gegenstand dieser Arbeit ist die kanonische Verbindung klassischer globaler Schwerefeldmodellierung in der Konzeption von Stokes (1849) und Neumann (1887) und moderner lokaler Multiskalenberechnung mittels lokalkompakter adaptiver Wavelets. Besonderes Anliegen ist die "Zoom-in"-Ermittlung von Geoidhöhen aus lokal gegebenen Schwereanomalien bzw. Schwerestörungen.
We develop a framework for analyzing an executive’s own-company stockholding and work effort preferences. The executive, characterized by risk aversion and work effectiveness parameters, invests his personal wealth without constraint in the financial market, including the stock of his own company whose value he can directly influence with work effort. The executive’s utility-maximizing personal investment and work effort strategy is derived in closed-form, and an indifference utility rationale is demonstrated to determine his required compensation. Our results have implications for the practical and theoretical assessment of executive quality and the benefits of performance contracting. Assuming knowledge of the company’s non-systematic risk, our executive’s unconstrained own-company investment identifies his work effectiveness (i.e. quality), and also reflects work effort that establishes a base-level that performance contracting should seek to exceed.
We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it depends on the graph topology and the number of users. In our context best and worst equilibria are those with minimum respectively maximum total latency. We establish that both problems can be solved by a Greedy algorithm with a suitable tie breaking rule on parallel links. On series-parallel graphs finding a worst Nash equilibrium is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. Additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph.
The purpose of this paper is the canonical connection of classical global gravity field determination following the concept of Stokes (1849), Bruns (1878), and Neumann (1887) on the one hand and modern locally oriented multiscale computation by use of adaptive locally supported wavelets on the other hand. Essential tools are regularization methods of the Green, Neumann, and Stokes integral representations. The multiscale approximation is guaranteed simply as linear difference scheme by use of Green, Neumann, and Stokes wavelets, respectively. As an application, gravity anomalies caused by plumes are investigated for the Hawaiian and Iceland areas.
An easy numerical handling of time-dependent problems with complicated geometries, free moving boundaries and interfaces, or oscillating solutions is of great importance for many applications, e.g., in fluid dynamics (free surface and multiphase flows, fluid-structure interactions [22, 18, 24]), failure mechanics (crack growth and propagation ), magnetohydrodynamics (accretion disks, jets and cloud simulation ), biophysics and -chemistry. Appropriate discretizations, so-called mesh-less methods, have been developed during the last decades to meet these challenging demands and to relieve the burden of remeshing and successive mesh generation being faced by the conventional mesh-based methods, [16, 10, 3]. The prearranged mesh is an artificial constraint to ensure compatibility of the mesh-based interpolant schemes, that often conflicts with the real physical conditions of the continuum model. Then, remeshing becomes inevitable, which is not only extremely time- and storage consuming but also the source for numerical errors and hence the gradual loss of computational accuracy. Apart from this advantage, mesh-less methods also lead to fundamentally better approximations regarding aspects, such as smoothness, nonlocal interpolation character, flexible connectivity, refinement and enrichment procedures, . The common idea of mesh-less methods is the discretization of the domain of interest by a finite set of independent, randomly distributed particles moving with a characteristic velocity of the problem. Location and distribution of the particles then account for the time-dependent description of the geometry, data and solution. Thereby, the global solution is linearly superposed from the local information carried by the particles. In classical particle methods [20, 21], the respective weight functions are Dirac distributions which yield solutions in a distributional sense.
Recently we developed a discrete model of elastic rods with symmetric cross section suitable for a fast simulation of quasistatic deformations . The model is based on Kirchhoff’s geometrically exact theory of rods. Unlike simple models of “mass & spring” type typically used in VR applications, our model provides a proper coupling of bending and torsion. The computational approach comprises a variational formulation combined with a finite difference discretization of the continuum model. Approximate solutions of the equilibrium equations for sequentially varying boundary conditions are obtained by means of energy minimization using a nonlinear CG method. As the computational performance of our model yields solution times within the range of milliseconds, our approach proves to be sufficient to simulate an interactive manipulation of such flexible rods in virtual reality applications in real time.