Major histocompatibility complex (MHC) protein analysis by optimised two-dimensional electrophoretic methods

Human histocompatibility molecules HLA-Class I and Class II (DR, DQ, DP) were analysed using three two-dimensional protocols: nonequilibrium pH gradient electrophoresis (NEPHGE), isoelectric focusing-acidic gradient (IEF-AG) and isoelectric focusing-basic gradient (IEF-BG). The three methods differ in their carrier ampholyte combinations and electrophoretic conditions. They provide different pH gradients and therefore different electrofocusing profiles. The NEPHGE protocol was adequate for separating proteins across a broad range of pI mobilities, i.e. 4.4 pH units between the acidic and the basic end. In contrast, the IEF-AG and the IEF-BG protocols gave a separation power across a narrow pH range, 1.9 and 1.7 pH units respectively. Thus, whereas the NEPHGE protocol provides a tool for a global major histocompatibility complex (MHC) antigen profile analysis, the IEF-AG and -BG allows one to investigate subcomponents of the individual MHC chains. For example, NEPHGE analysis of the HLA Class I heavy chain revealed a single spot. However, IEF-BG revealed the presence of six equidistantly spaced spots spanning a short pH gradient with identical molecular weight. Similar improved resolution was seen for the HLA-DR, DQ, and DP molecules. The IEF acidic gradient was adequate for separating the alpha chain; the IEF basic gradient gave better resolution of the beta chains. This data provides a baseline set of conditions for both analytical and preparative MHC protein studies prior to amino acid sequencing.     

Semidefinite and linear programming integrality gaps for scheduling identical machines

Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lovász and Schrijver (SIAM J Optim 1:166–190, 1991) developed systematic procedures to construct the hierarchies of relaxations known as lift-and-project methods. They have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the problem of scheduling identical machines to minimize the makespan. First we show that the configuration LP has an integrality gap of at least 1024/1023 by providing a family of instances with 15 different job sizes. Then we show that for any integer n there is an instance with n jobs in this family such that after \(\varOmega (n)\) rounds of the Sherali–Adams (\(\text {SA}\)) or the Lovász–Schrijver (\(\text {LS}_+\)) hierarchy the integrality gap remains at least 1024/1023.     

An unbounded Sum-of-Squares hierarchy integrality gap for a polynomially solvable problem

In this expository article, we study optimization problems specified via linear and relative entropy inequalities. Such relative entropy programs (REPs) are convex optimization problems as the relative entropy function is jointly convex with respect to both its arguments. Prominent families of convex programs such as geometric programs (GPs), second-order cone programs, and entropy maximization problems are special cases of REPs, although REPs are more general than these classes of problems. We provide solutions based on REPs to a range of problems such as permanent maximization, robust optimization formulations of GPs, and hitting-time estimation in dynamical systems. We survey previous approaches to some of these problems and the limitations of those methods, and we highlight the more powerful generalizations afforded by REPs. We conclude with a discussion of quantum analogs of the relative entropy function, including a review of the similarities and distinctions with respect to the classical case. We also describe a stylized application of quantum relative entropy optimization that exploits the joint convexity of the quantum relative entropy function.     

A technique for obtaining true approximations for k-center with covering constraints

Mathematical Programming - There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem...     

Optimization Over the Boolean Hypercube Via Sums of Nonnegative Circuit Polynomials

Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube. One particularly successful way to prove complexity bounds for these types of problems is based on sums of squares (SOS) as nonnegativity certificates. In this article, we initiate optimization problems over the boolean hypercube via a recent, alternative certificate called sums of nonnegative circuit polynomials (SONC). We show that key results for SOS-based certificates remain valid: First, for polynomials, which are nonnegative over the n-variate boolean hypercube with constraints of degree d there exists a SONC certificate of degree at most \(n+d\). Second, if there exists a degree d SONC certificate for nonnegativity of a polynomial over the boolean hypercube, then there also exists a short degree d SONC certificate that includes at most \(n^{O(d)}\) nonnegative circuit polynomials. Moreover, we prove that, in opposite to SOS, the SONC cone is not closed under taking affine transformation of variables and that for SONC there does not exist an equivalent to Putinar’s Positivstellensatz for SOS. We discuss these results from both the algebraic and the optimization perspective.

     

The conservation energy principle in description of stable and unstable states for aluminium

In the paper the physical model based on the energy conservation principle is proposed. On the basis of this principle the division of energy on volumetric and deviatory parts is presented. In this model a concept of energy division is recognised as important. Using the strain energy density function we can formulate criteria of the material equilibrium stability. Considerations are carried out for aluminium. All assumptions are based on uniaxial tension test supported by transverse deformation measurements. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)