A 5/4 algorithm for two-dimensional packing

This paper proposes a new algorithm for a two-dimensional packing problem first studied by Baker, Coffman, and Rivest (SIAM J. Comput. 9, No. 4(1980), 846–855). In their model, a finite list of rectangles is to be packed into a rectangular bin of finite width but infinite height. The model has applications to certain scheduling and stock-cutting problems. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding polynomial approximation algorithms for the problem, i.e., algorithms which come within a constant times the height used by an optimal packing. For the algorithm proposed in this paper, the ratio of the height obtained by the algorithm and the height used by an optimal packing is asymptotically bounded by 5/4. This bound is an improvement over the bound of 4/3 achieved by the best previous algorithm.     

An O(n2log n) parallel max-flow algorithm

A synchronized parallel algorithm for finding maximum flow in a directed flow network is presented. Its depth is $\text{O(}\text{n}{}^3\text{(}\text{log}\text{n)}\text{p)}$, where p (p ≤ n) is the number of processors used. This problem seems to be more involved than most of the problems for which efficient parallel algorithms exist. The parallel algorithm induces a new rather simple sequential O(n³) algorithm. This algorithm is very much parallel oriented. It is quite difficult to conceive and analyze it, if one is restricted to the sequential point of view.     

Minimization problems in L1(R3)

In this paper, minimization problems in L¹($\text{R}$³) are considered. These problems arise in astrophysics for the determination of equilibrium configurations of axially symmetric rotating fluids (rotating stars). Under nearly optimal assumptions a minimizer is proved to exist by a direct variational method, which heavily uses the symmetry of the problem in order to get some compactness. Finally, by looking directly at the Euler equation, we give some existence results (of solutions of the Euler equation) even if the infimum is not finite.     

Algorithms for maximum independent sets

An algorithm is presented which finds (the size of) a maximum independent set of an n vertex graph in time O(2^0.276n) improving on a previous bound of $\text{O(2}{}^{\mathrm{<mtext>n</mtext><mtext>3</mtext>}}\text{)}$. The improvement comes principally from three sources: first, a modified recursive algorithm based on a more detailed study of the possible subgraphs around a chosen vertex; second, an improvement, not in the algorithm but in the time bound proved, by an argument about connected regular graphs; third, a time-space trade-off which can speed up recursive algorithms from a fairly wide class.     

Ring structures and the discrete Fourier transform

Since the pioneering work of J. W. Cooley and J. W. Tukey Math. Comp.19 1965 297–301, a great deal of effort has been devoted to developing efficient algorithms for computing finite Fourier transform. Among the new methods suggested over the past several years, methods depending on ring-theoretic structures have received special attention. This approach, originally suggested by C. Rader (Proc. IEEE5, 6 1968, 1107–1108), was really developed by S. Winograd (“Arithmetic Complexity of Computations,” CBMS-NSF Regional Conference Series in Applied Mathematics 1980 into a powerful new algorithm. Winograd's real contribution was to realize that there are efficient algorithms to evaluate cyclic convolution. The purpose of this article is twofold: first, to make more explicit the interplay between ring-theoretic structures and the algorithms for the finite Fourier transform; second, to use this new insight to construct new algorithms for evaluating the finite Fourier transform on the groups $\text{Z}\text{(p}{}^{\mathrm{s}}\text{Z)}\text{⊕}\text{Z}\text{(p}{}^{\mathrm{s}}\text{Z)}\text{⊕ … ⊕}\text{Z}\text{(p}{}^{\mathrm{s}}\text{Z)}$.     

A new proof for the first-fit decreasing bin-packing algorithm

This paper provides a new proof of a classical result of bin-packing, namely the $\text{11}\text{9}$ performance bound for the first-fit decreasing algorithm. In bin-packing, a list of real numbers in (0,1] is to be packed into a minimal number of bins, each of which holds a total of at most 1. The first-fit decreasing (FFD) algorithm packs each number in order of nonincreasing size into the first bin in which it fits. In his doctoral dissertation, D. S. Johnson (“Near-Optimal Bin Packing Algorithms,” Doctoral thesis, MIT, Cambridge, Mass., 1973) proved that for every list L, $\text{FFD}\text{(L) ?}\text{11}\text{9}\text{OPT}\text{(L) + 4}$, where FFD(L) and OPT(L) denote the number of bins used by FFD and an optimal packing, respectively. Unfortunately, his proof required more than 100 pages! This paper contains a much shorter and simpler proof that $\text{FFD}\text{(L) ?}\text{11}\text{9}\text{OPT}\text{(L) + 3}$.     

Properties of Hida processes on R2. 2. Prediction and interpolation problems for processes on R2

The properties of N-Hida processes Part 1 (B. Prum, 1984, J. Multivar. Anal.15, 336–360) are studied when the indices set is $\text{R}$². First, the past of a point (s, t) of $\text{R}$² is extended to $\text{G}$_st = σ{γ_uv, u ≤ s or v ≤ t}. The dimension of the linear space generated by the conditional expectations of an N-Hida process γ_z when z goes over a p × q lattice is bounded by N(p + q ? 1). The same problem is then considered when the expectations are taken conditionally to the field generated by the process outside of a rectangle, and the bound of the dimension of the linear space generated on a lattice is also given. Special attention is devoted to the case when γ_z is a combination of strong martingales.     

Simple components of group algebras Q[G] central over real quadratic fields

Let k be a real quadratic field, and $\text{U}$ a central division quaternion algebra over k. In this paper sufficient conditions are given to insure that $\text{U}$ appears in a simple component of the group algebra Q[G] of some finite group G over the rational field Q. In particular, when k is assumed to be Q(√2) or Q(√5), the necessary and sufficient conditions for $\text{U}$ to appear in some Q[G] are given.     

A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given.     

A 7160 theorem for bin packing

The FIRST FIT DECREASING algorithm for bin packing has long been famous for its guarantee that no packing it generates will use more than $\text{11}\text{9}\text{= 1.222…}$ times the optimal number of bins. We present a simple modified version that has essentially the same running time, should perform at least as well on average, and yet provides a guarantee of $\text{71}\text{60}\text{= 1.18333…}$.     

The iwasawa invariant μ in the composite of two Zl-extensions

Let k₀ be a finite extension field of the rational numbers, and assume k₀ has at least two Z_l-extensions. Assume that at least one Z_l-extension $\text{K}\text{k}{}_0$ has Iwasawa invariant μ = 0, and let L be the composite of K and some other Z_l-extension of k₀. In this paper we find an upper bound for the number of Z_l-extensions of k₀ contained in L with nonzero μ.     

An upper bound on the Ramsey numbers R(3, k)

Ajtai, Komlós, and Szemerédi (J. Combin. Theory Ser. A29 (1980), 354–360) recently announced that $\text{R(3, k) <}\text{100k}{}^2\text{ln}\text{k}$. This follows from the discovery of a (polynomial) algorithm to find in any triangle-free graph on n vertices with average degree t an independent set of size at least $\text{n}\text{ln}\text{t}\text{100t}$. Here, their algorithm is modified to improve both bounds, replacing 100 by 2.4, and carefully working out the details of the proof.     

C1-algebras with finite duals

A forest is a finite partially ordered set F such that for x, y, z?F with x ? z, y ? z one has x ? y or y ? x. In this paper we give a complete characterization of all separable C¹-algebras $\text{A}$ with a finite dual $\text{A}\text{?}$, for which Prim $\text{A}$ is a forest with inclusion as partial order. These results are extended to certain separable C¹-algebras $\text{A}$ with a countable dual$\text{A}\text{?}$. As an example these results are used to characterize completely all separable C¹-algebras $\text{A}$ with a three point dual.     

The value of L(12, χ) for Abelian L-functions of complex quadratic fields

It is shown that the values of Abelian L-functions of complex quadratic fields at $\text{s =}\text{1}\text{2}$ can be expressed as finite sums of values of a non-holomorphic modular form at certain special points in the Poincare upper half-plane. It is also shown that these values are related to a Petersson inner product. From this relation a criterion is derived for the vanishing at $\text{s =}\text{1}\text{2}$ of the Dedekind zeta function for the non-cyclic cubic extensions of the rational field.     

C1-algebras without idempotents

The simplest statement of the main results are these: Let π be a free group on 2 generators. Let Cπ be the complex ring and L¹π the ring extension to L¹ sums. Then L¹π contains no idempotents. Furthermore, if α ? Cπ, β?L¹π are nonzero, then αβ ≠ 0. The first result is in the direction of proving that a certain simple $\text{C}{}^1\text{-}\text{algebra}$ has no idempotents yielding a counter-example to the suggestion that simple $\text{C}{}^1\text{-}\text{algebras}$ are generated by their projections.     

Version continue de l'algorithme d'Uzawa

In Carlier et al. (ESAIM Proceedings, CEMRACS 1999), an algorithm was proposed to approximate the projection of a function $\text{f∈H}{}^1{}_0\text{(Ω)}$ (where $\text{Ω}$ is a convex domain) onto the cone of convex functions. This algorithm is based on a dual expression of the constraint, which leads to a saddle-point problem which has no solution in general. We show here that the Uzawa algorithm for this saddle-point problem can be seen as the semi-discretization of an evolution equation

$\text{d}\text{λ}\text{d}\text{t}\text{+?Ψ(λ)?0,}$

where Ψ is a convex, l.s.c., proper function. In case the saddle-point problem has no solution, one has $\text{0∈}\text{R(?Ψ)}$ but ?Ψ^?1(0)=?. We establish that λ(t) is then divergent, and that a subsequence of the associated trajectory in the primal space converges weakly to the solution of the initial projection problem. To cite this article: B. Maury, C. R. Acad. Sci. Paris, Ser. I 337 (2003).