A Fubini theorem

Let I₀ be the σ-ideal of subsets of a Polish group generated by Borel sets which have perfectly many pairwise disjoint translates. We prove that a Fubini-type theorem holds between I₀ and the σ-ideals of Haar measure zero sets and of meager sets. We use this result to give a simple proof of a generalization of a theorem of Balcerzak-Ros?anowski-Shelah stating that I₀ on N² strongly violates the countable chain condition.     

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.     

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.     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.