Adding cardinality constraints to integer programs with applications to maximum satisfiability

Max-SAT-CC is the following optimization problem: Given a formula in CNF and a bound k, find an assignment with at most k variables being set to true that maximizes the number of satisfied clauses among all such assignments. If each clause is restricted to have at most ? literals, we obtain the problem Max-?SAT-CC. Sviridenko [Algorithmica 30 (3) (2001) 398-405] designed a (1−e⁻¹)-approximation algorithm for Max-SAT-CC. This result is tight unless P=NP [U. Feige, J. ACM 45 (4) (1998) 634-652]. Sviridenko asked if it is possible to achieve a better approximation ratio in the case of Max-?SAT-CC. We answer this question in the affirmative by presenting a randomized approximation algorithm whose approximation ratio is . To do this, we develop a general technique for adding a cardinality constraint to certain integer programs. Our algorithm can be derandomized using pairwise independent random variables with small probability space.     

t-Private and t-secure Auctions

In most of the auction systems the values of bids are known to the auctioneer. This allows him to manipulate the outcome of the auction. Hence, one might be interested in hiding these values. Some cryptographically secure protocols for electronic auctions have been presented in the last decade. Our work extends these protocols in several ways. On the basis of garbled circuits, i.e., encrypted circuits, we present protocols for sealed-bid auctions that fulfill the following requirements: 1) protocols are information-theoretically t-private for honest but curious parties; 2) the number of bits that can be learned by malicious adversaries is bounded by the output length of the auction; 3) the computational requirements for participating parties are very low: only random bit choices and bitwise computation of the XOR-function are necessary. Note that one can distinguish between the protocol that generates a garbled circuit for an auction and the protocol to evaluate the auction. In this paper we address both problems. We will present a t-private protocol for the construction of a garbled circuit that reaches the lower bound of 2t 1 parties, and a more randomness effcient protocol for (t 1)2 parties. Finally, we address the problem of bid changes in an auction.     

Tracing pathway activities with kinase inhibitors and reverse phase protein arrays

Controlling aberrant protein kinase activity is a promising strategy for a variety of diseases, particularly cancer. Hence, the development of kinase inhibitors is currently a focal point for pharmaceutical research. In this study we utilize a chip-based reverse phase protein array (RPA) platform for profiling of kinase inhibitors in cell-based assays. In combination with the planar wave-guide technology the assay system has an absolute LOD down to the low zeptomole range. A431 cell lysates were analyzed for the activation state of key effectors in the epidermal growth factor (EGF) and insulin signaling pathways to validate this model for compound screening. A microtiter-plate format for growing, treating, and lysing cells was shown to be suitable for this approach, establishing the value of the technology as a screening tool for characterization of large numbers of kinase inhibitors against a wide variety of cellular signaling pathways. Moreover, the reverse array format allows rapid development of site-specific phosphorylation assays, since in contrast to ELISA type systems only a single antigen-specific antibody is required.     

Application of the general elimination method in robot kinematics

A general method for solving the robot inverse kinematics problem is presented. The method is based upon the general elimination method to obtain the equivalent system of equations which are triangularized and the solutions of the inverse kinematics problem can be solved by backsubstitutions.     

Introduction of lysine residues on the light chain constant domain improves the labelling properties of a recombinant Fab fragment

Europium chelates provide a non-radioactive alternative forsensitive labelling of antibodies for diagnostic immunoassays.Lysine residues at antibody surfaces are ready targets for labellingby an isothiocyanate derivative of the europium chelate (Eu³⁺).Here the labelling efficiency of a recombinant anti-human -fetoprotein(hAFP) Fab fragment has been improved by increasing its lysinecontent by protein engineering. Molecular modelling was usedto identify three light chain constant domain surface arginineresidues, R154, R187 and R210, which were mutated to lysineresidues. The mutations did not influence the affinity of thelysine-enriched Fab fragment and its labelling efficiency wasfound to be 40% higher than that of the wildtype Fab fragmentWith low degree of labelling, the affinities of the two Fabfragments were identical and comparable with that of the originalmonoclonal anti-hAFP IgG. With a higher degree of labellingthe affinities of both Fab fragments decreased more than thatof the intact IgG since more lysine residues are available forlabelling in the additional heavy chain constant domains ofthe larger molecule. Electrostatic adsorption and covalent immobilizationof the Fab fragments were characterized by BIAcore^TM and thelysine-enriched Fab fragment was found to be more efficientlyimmobilized to an activated carboxymethyl surface.     

Estimating shear properties of walnut wood: a combined experimental and theoretical approach

In this study, several theoretical models to numerically estimate shear properties of orthotropic materials are introduced. These approaches are based on the combination of Hankinson’s empirically derived formula with other empirical and analytical calculations. Next to shear moduli, which are estimated from the elastic moduli and Poisson’s ratios, shear strengths are also estimated from the in-axis strengths. The models are validated by mechanical tests on walnut wood (Juglans regia L.), for which a sufficient data set can be found in literature. The Arcan test is used to estimate the shear moduli, while the shear block test is used to estimate the shear strengths. The results show that the model, which is based on a combined use of Hankinson’s formula and tensor rotation, gives the best estimation of shear moduli as evaluated by the minimum differences to the experimentally obtained results. For the shear strengths, a combination of Hankinson’s formula and Norris’ failure criterion shows the best agreement in comparison to the experimental data. The theoretical calculations may be used for a time efficient estimation of shear modulus and strength in comparison to the very time-consuming experimental estimation.     

Excluded volume effects in on‐ and off‐lattice reaction–diffusion models

Mathematical models are important tools to study the excluded volume effects on reaction–diffusion systems, which are known to play an important role inside living cells. Detailed microscopic simulations with off‐lattice Brownian dynamics become computationally expensive in crowded environments. In this study, the authors therefore investigate to which extent on‐lattice approximations, the so‐called cellular automata models, can be used to simulate reactions and diffusion in the presence of crowding molecules. They show that the diffusion is most severely slowed down in the off‐lattice model, since randomly distributed obstacles effectively exclude more volume than those ordered on an artificial grid. Crowded reaction rates can be both increased and decreased by the grid structure and it proves important to model the molecules with realistic sizes when excluded volume is taken into account. The grid artefacts increase with increasing crowder density and they conclude that the computationally more efficient on‐lattice simulations are accurate approximations only for low crowder densities.Inspec keywords: reaction‐diffusion systems, cellular biophysics, biodiffusion, Brownian motion, cellular automata, molecular biophysics, molecular configurationsOther keywords: crowder density, grid artefacts, grid structure, crowded reaction rates, artificial grid, randomly distributed obstacles, crowding molecules, cellular automata models, on‐lattice approximations, crowded environments, off‐lattice Brownian dynamics, detailed microscopic simulations, living cells, mathematical models, off‐lattice reaction‐diffusion models, on‐lattice reaction‐diffusion models, excluded volume effects     

Noncontact Sonic NDE and Defect Imaging Via Local Defect Resonance

A selective acoustic activation of defects based on the concept of local defect resonance enables to enhance considerably the intensity of defect vibrations and makes it possible to reduce the input acoustic powers to the levels permissible for noncontact nondestructive inspection. Since for cm-size defects in composite materials, the LDR frequencies lie in the low kHz-range, the resonant noncontact activation shifts to an audible frequency range and can be provided by conventional sonic equipment. In this paper, the feasibility of the resonant noncontact inspection is validated for the most “problematic” methodologies of nonlinear, thermosonic and shearosonic NDE that usually require an elevated acoustic power and, therefore, a reliable contact between the specimen and the transducer. In contrast, the noncontact versions developed employ commercial loudspeakers which can simultaneously insonify large areas and be applied for a contactless sonic inspection of different materials and various scale components.     

Model‐based reconstruction for T1 mapping using single‐shot inversion‐recovery radial FLASH

Quantitative parameter mapping in MRI is typically performed as a two‐step procedure where serial imaging is followed by pixelwise model fitting. In contrast, model‐based reconstructions directly reconstruct parameter maps from raw data without explicit image reconstruction. Here, we propose a method that determines T1 maps directly from multi‐channel raw data as obtained by a single‐shot inversion‐recovery radial FLASH acquisition with a Golden Angle view order. Joint reconstruction of a T1, spin‐density and flip‐angle map is formulated as a nonlinear inverse problem and solved by the iteratively regularized Gauss‐Newton method. Coil sensitivity profiles are determined from the same data in a preparatory step of the reconstruction. Validations included numerical simulations, in vitro MRI studies of an experimental T1 phantom, and in vivo studies of brain and abdomen of healthy subjects at a field strength of 3 T. The results obtained for a numerical and experimental phantom demonstrated excellent accuracy and precision of model‐based T1 mapping. In vivo studies allowed for high‐resolution T1 mapping of human brain (0.5–0.75 mm in‐plane, 4 mm section thickness) and liver (1.0 mm, 5 mm section) within 3.6–5 s. In conclusion, the proposed method for model‐based T1 mapping may become an alternative to two‐step techniques, which rely on model fitting after serial image reconstruction. More extensive clinical trials now require accelerated computation and online implementation of the algorithm. © 2016 Wiley Periodicals, Inc. Int J Imaging Syst Technol, 26, 254–263, 2016