Exact solutions to linear programming problems

The use of floating-point calculations limits the accuracy of solutions obtained by standard LP software. We present a simplex-based algorithm that returns exact rational solutions, taking advantage of the speed of floating-point calculations and attempting to minimize the operations performed in rational arithmetic. Extensive computational results are presented.     

The Riesz decomposition of finely superharmonic functions

This paper answers a question of Fuglede about minimal positive harmonic functions associated with irregular boundary points. As a consequence, an old and central problem of fine potential theory, concerning the Riesz decomposition, is resolved. Namely, it is shown that, on certain fine domains, there exist positive finely superharmonic functions which do not admit any positive finely harmonic minorant and yet are not fine potentials.     

C59N单分子整流器

通过将单个C59N分子置于双势垒隧道结中，从而利用单电子隧穿效应和C59N分子的特殊能级结构，我们成功地实现了一种新型的单分子整流器件．实验中这个整流器件的正向导通电压约为0．5-0．7V，反向击穿电压约为1．6—1．8V．理论分析表明，中性C59N分子的半占据费米能级以及在不同充电情况下费米能级的不对称移动是形成整流效应的主要原因．其构成原理也决定了该器件具有稳定、易重复的特点．     

Fire containment in grids of dimension three and higher

We consider a deterministic discrete-time model of fire spread introduced by Hartnell [Firefighter! an application of domination, Presentation, in: 20th Conference on Numerical Mathematics and Computing, University of Manitoba in Winnipeg, Canada, September 1995] and the problem of minimizing the number of burnt vertices when a fixed number of vertices can be defended by firefighters per time step. While only two firefighters per time step are needed in the two-dimensional lattice to contain any outbreak, we prove a conjecture of Wang and Moeller [Fire control on graphs, J. Combin. Math. Combin. Comput. 41 (2002) 19-34] that 2d-1 firefighters per time step are needed to contain a fire outbreak starting at a single vertex in the d-dimensional square lattice for d?3; we also prove that in the d-dimensional lattice, d?3, for each positive integer f there is some outbreak of fire such that f firefighters per time step are insufficient to contain the outbreak. We prove another conjecture of Wang and Moeller that the proportion of elements in the three-dimensional grid P_n×P_n×P_n which can be saved with one firefighter per time step when an outbreak starts at one vertex goes to 0 as n gets large. Finally, we use integer programming to prove results about the minimum number of time steps needed and minimum number of burnt vertices when containing a fire outbreak in the two-dimensional square lattice with two firefighters per time step.     

The essential Lagrangian-Grassmannian and the homotopy type of the Fredholm Lagrangian-Grassmannian

Let H be a separable infinite dimensional Hilbert space endowed with a symplectic structure and let L₀⊂H be a Lagrangian subspace. Using the results of [A. Abbondandolo, P. Majer, Infinite dimensional Grassmannians, math.AT/0307192], we show that the Fredholm Lagrangian-Grassmannian FL₀(Λ) has the homotopy type of Gc(L₀), the Grassmannian of all Lagrangian subspaces of H that are compact perturbations of L₀. It is well known that the latter has the homotopy type of the quotient U(∞)/O(∞). As a corollary, we recover a result by B. Booss-Bavnbek and K. Furutani (see [B. Booss-Bavnbek, K. Furutani, Symplectic functional analysis and spectral invariants, Contemp. Math. 242 (1999) 53-83; K. Furutani, Fredholm-Lagrangian-Grassmannian and the Maslov index, J. Geom. Phys. 51 (2004) 269-331]) that the L₀-Maslov index is an isomorphism between the fundamental group of FL₀(Λ) and the integers.     

Some geometrical aspects of semidefinite linear complementarity problems

This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R₀-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically.     

The communication complexity of private value single-item auctions

This paper is concerned with information revelation in single-item auctions. We compute how much data needs to be transmitted in three strategically equivalent auctions—the Vickrey auction, the English auction and the recently proposed bisection auction—and show that in the truth-telling equilibrium the bisection auction is the best performer.     

Barycentric systems and stretchability

Using a general resolution of barycentric systems we give a generalization of Tutte's theorem on convex drawing of planar graphs. We deduce a characterization of the edge coverings into pairwise non-crossing paths which are stretchable: such a system is stretchable if and only if each subsystem of at least two paths has at least three free vertices (vertices of the outer face of the induced subgraph which are internal to none of the paths of the subsystem). We also deduce that a contact system of pseudo-segments is stretchable if and only if it is extendible.     

Roots,iterations and logarithms of formal automorphisms

In this paper it is proved that having a logarithm is equivalent to having roots of arbitrary order in the group of automorphisms of a formal power series ring, and in algebraic subgroups too