The primal-dual method for approximation algorithms

In this survey, we give an overview of a technique used to design and analyze algorithms that provide approximate solutions to NP-hard problems in combinatorial optimization. Because of parallels with the primal-dual method commonly used in combinatorial optimization, we call it the primal-dual method for approximation algorithms. We show how this technique can be used to derive approximation algorithms for a number of different problems, including network design problems, feedback vertex set problems, and facility location problems. Received: June 19, 2000 / Accepted: February 7, 2001?Published online October 2, 2001     

A topological aspect of Sobolev mappings

Let be a connected open set, . We give a sufficient condition for a mapping , , to have the property that sgn is almost everywhere of one sign. Following the work of Müller, Spector, and Tang [MST], we give an application of our results to the theory of non-linear elasticity. Received: 13 October 2000 / Accepted: 23 January 2001 / Published online: 4 May 2001     

Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations

Summary. We examine the convergence characteristics of iterative methods based on a new preconditioning operator for solving the linear systems arising from discretization and linearization of the steady-state Navier-Stokes equations. With a combination of analytic and empirical results, we study the effects of fundamental parameters on convergence. We demonstrate that the preconditioned problem has an eigenvalue distribution consisting of a tightly clustered set together with a small number of outliers. The structure of these distributions is independent of the discretization mesh size, but the cardinality of the set of outliers increases slowly as the viscosity becomes smaller. These characteristics are directly correlated with the convergence properties of iterative solvers. Received August 5, 2000 / Published online June 20, 2001     

The G/M/1 queue revisited

The G/M/1 queue is one of the classical models of queueing theory. The goal of this paper is two-fold: (a) To introduce new derivations of some well-known results, and (b) to present some new results for the G/M/1 queue and its variants. In particular, we pay attention to the G/M/1 queue with a set-up time at the start of each busy period, and the G/M/1 queue with exceptional first service. Dedicated to Arie Hordijk on his 65th birthday, in friendship and admiration.     

Deformations of incompressible bodies with free boundaries

Communicated by C. Dafermos     

Poincaré series and holomorphic averaging

Summary We provide an alternate proof of McMullen's theorem on contractive properties of the Poincaré series operator in the special case of the universal covering. This case includes in particular Kra's Theta Conjecture.Oblatum 16-X-1991 & 14-IV-1992First author supported in part by a grant from the National Science Foundation