An LP-based heuristic algorithm for the node capacitated in-tree packing problem

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard.We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate spanning in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the column generation method for the LP (linear programming) relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP relaxation problem and then improving them with a greedy algorithm. We analyze upper and lower bounds on the solution quality of such LP-based algorithms for this problem.We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods.     

Practical rearrangement methods for dynamic double‐array dictionaries

Double‐array structures have been widely used to implement dictionaries with string keys. Although the space efficiency of dynamic double‐array dictionaries tends to decrease with key updates, we can still maintain high efficiency using existing methods. However, these methods have practical problems of time and functionality. This paper presents several efficient rearrangement methods to solve these problems. Through experiments using real‐world datasets, we demonstrate that the proposed rearrangement methods are much more practical than existing methods.     

Towards development of enhanced fully-Lagrangian mesh-free computational methods for fluid-structure interaction

Simulation of incompressible fluid flow-elastic structure interactions is targeted by using fully-Lagrangian mesh-free computational methods. A projection-based fluid model(moving particle semi-implicit(MPS)) is coupled with either a Newtonian or a Hamiltonian Lagrangian structure model(MPS or HMPS) in a mathematically-physically consistent manner. The fluid model is founded on the solution of Navier-Stokes and continuity equations. The structure models are configured either in the framework of Newtonian mechanics on the basis of conservation of linear and angular momenta, or Hamiltonian mechanics on the basis of variational principle for incompressible elastodynamics. A set of enhanced schemes are incorporated for projection-based fluid model(Enhanced MPS), thus, the developed coupled solvers for fluid structure interaction(FSI) are referred to as Enhanced MPS-MPS and Enhanced MPS-HMPS. Besides, two smoothed particle hydrodynamics(SPH)-based FSI solvers, being developed by the authors, are considered and their potential applicability and comparable performance are briefly discussed in comparison with MPS-based FSI solvers. The SPH-based FSI solvers are established through coupling of projection-based incompressible SPH(ISPH) fluid model and SPH-based Newtonian/Hamiltonian structure models, leading to Enhanced ISPH-SPH and Enhanced ISPH-HSPH. A comparative study is carried out on the performances of the FSI solvers through a set of benchmark tests, including hydrostatic water column on an elastic plate,high speed impact of an elastic aluminum beam, hydroelastic slamming of a marine panel and dam break with elastic gate.     

Targeted proteome analysis of microalgae under high-light conditions by optimized protein extraction of photosynthetic organisms

1. Download high-res image (294KB)
2. Download full-size image