Approximate minimum-cost multicommodity flows in\tilde O(ɛ −2 KNM) timetime

We show that an ε-approximate solution of the cost-constrainedK-commodity flow problem on anN-nodeM-arc network,G can be computed by sequentially solving O(K(? ^?2+logGK) logGM log (G? ^?1 GK)) single-commodity minimum-cost flow problems on the same network. In particular, an approximate minimum-cost multicommodity flow can be computed in $\tilde O$ (G? ^?2 GKNM) running time, where the notation Õ(·) means “up to logarithmic factors”. This result improves the time bound mentioned by Grigoriadis and Khachiyan [4] by a factor ofM/N and that developed more recently by Karger and Plotkin [8] by a factor of? ^?1. We also provide a simple $\tilde O$ (NM)-time algorithm for single-commodity budget-constrained minimum-cost flows which is $\tilde O$ (? ^?3) times faster than the algorithm developed in the latter paper.     

Easy α- to β-migration of an enol moiety on a pyrrole ring

Functionalized pyrrolic enols, 2-(2,2-dicyano-1-hydroxyethenyl)-1-methylpyrroles, synthesized from 2-ethenylpyrroles by a nucleophilic SEt-OH exchange, upon heating (75-142 °C) are readily rearranged to their 3-isomers in near to quantitative yield. The inter or intramolecular auto-protonation of a pyrrole ring by the acidic enol hydroxyl to form a mesomeric pyrrolium cation or zwitterion is suggested to be a key step in the rearrangement.     

Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank

We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for ``infinite-dimensional second-order cone programs.' We consider as an example a long-step primal-dual algorithm based on the Nesterov-Todd direction. It is shown that this algorithm can be generalized along with complexity estimates to the infinite-dimensional situation under consideration. An application is given to an important problem of control theory: multi-criteria analytic design of the linear regulator. The calculation of the Nesterov-Todd direction requires in this case solving one matrix differential Riccati equation plus solving a finite-dimensional system of linear algebraic equations on each iteration. The number of equations and unknown variables of this algebraic system is m+1, where m is a number of quadratic performance criteria. Key words.polynomial-time primal-dual interior-point methods – JB-algebras – infinite-dimensional problems – optimal control problemsThis author was supported in part by DMS98-03191 and DMS01-02698.This author was supported in part by the Grant-in-Aid for Scientific Research (C) 11680463 of the Ministry of Education, Culture, Sports, Science and Technology of Japan.Mathematics Subject Classification (1991):90C51, 90C48, 34H05, 49N05     

A New Inertia Theorem for Stein Equations,Inertia of Invertible Hermitian Block Toeplitz Matrices and Matrix Orthogonal Polynomials

In this paper we present an inertia result for Stein equations with an indefinite right hand side. This result is applied to establish connnections between the inertia of invertible hermitian block Toeplitz matrices and associated orthogonal polynomials.     

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most ^p+1, where is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors in the product of n lattices =₁××_n, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into . We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x=₁××_n for a system of polymatroid inequalities does not exceed max{Q,^logt/c(2Q,)}, where is the number of minimal feasible vectors for the system, , , and c(,) is the unique positive root of the equation 2^c(^c/log–1)=1. This bound is nearly sharp for the Boolean case ={0,1}ⁿ, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides . This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000):20E28, 20G40, 20C20     

On Effective Conductivity on ℤ d Lattice

We study the effective conductivity _e for a random wire problem on the d-dimensional cubic lattice ^d , d2 in the case when random conductivities on bonds are independent identically distributed random variables. We give exact expressions for the expansion of the effective conductivity in terms of the moments of the disorder parameter up to the 5th order. In the 2D case using the duality symmetry we also derive the 6th order expansion. We compare our results with the Bruggeman approximation and show that in the 2D case it coincides with the exact solution up to the terms of 4th order but deviates from it for the higher order terms.     

Survival of Virus Particles in Water Droplets: Hydrophobic Forces and Landauer’s Principle

Many small biological objects, such as viruses, survive in a water environment and cannot remain active in dry air without condensation of water vapor. From a physical point of view, these objects belong to the mesoscale, where small thermal fluctuations with the characteristic kinetic energy of k_BT (where k_B is the Boltzmann’s constant and T is the absolute temperature) play a significant role. The self-assembly of viruses, including protein folding and the formation of a protein capsid and lipid bilayer membrane, is controlled by hydrophobic forces (i.e., the repulsing forces between hydrophobic particles and regions of molecules) in a water environment. Hydrophobic forces are entropic, and they are driven by a system’s tendency to attain the maximum disordered state. On the other hand, in information systems, entropic forces are responsible for erasing information, if the energy barrier between two states of a switch is on the order of k_BT, which is referred to as Landauer’s principle. We treated hydrophobic interactions responsible for the self-assembly of viruses as an information-processing mechanism. We further showed a similarity of these submicron-scale processes with the self-assembly in colloidal crystals, droplet clusters, and liquid marbles.