Upper bounds and lowerbounds for the online postman problem
Piotr Berman and Junichiro Fukuyama

Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Flow Networks
Susanne Albers and Carsten Witt

A simple dual ascent algorithm for the multilevel facility location problem
A.F.Bumb and W.Kern

Minimizing Average Completion of Dedicated Tasks and Partially Ordered Sets
M. M. Halldorsson and G. Kortsarz and H. Shachnai

On the Equivalence Between the Primal-Dual Schema and the Local-Ratio Technique
Reuven Bar-Yehuda and Dror Rawitz

Approximation schemes for correlated vector packing problems
Alberto Caprara and Hans Kellerer and Ulrich Pferschy

A $3/2$-approximation algorithm for augmenting the edge connectivity from 1 to 2 using a subset of a given edge set
Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov

Incremental Codes
Yevgeniy Dodis and Shai Halevi

Online Weighted Flow Time and Deadline Scheduling
Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela and Kirk Pruhs

The maximum acyclic subgraph problem and degree-3 graphs
Alantha Newman

Some approximation results for the maximum agreement forest problem
E. M. Rodrigues and M-F. Sagot and Y. Wakabayashi

A Greedy Facility Location Algorithm Analyzed Using Dual Fitting
Mohammad Mahdian and Evangelos Markakis and Amin Saberi and Vijay Vazirani

0.863-Approximation Algorithm for MAX DICUT
Shiro Matuura and Tomomi Matsui

Approximation Algorithms for Budget-Constrained Auctions
Rahul Garg and Vijay Kumar and Vinayaka Pandit
 

Andreas Baltz and Tomasz Schoen and Anand Srivastav
On the b-partite Random Asymmetric Traveling Salesman Problem and its Assignment Relaxation

Don Coppersmith
L infinity embeddings

Lars Engebretsen
The Non-Approximability of Non-Boolean Predicates

Michal Parnas and Dana Ron and Alex Samorodnitsky
Proclaiming Dictators and Juntas or Testing Boolean Formulae

Michal Parnas and Dana Ron and Ronitt Rubinfeld
Testing Parenthesis Languages

K. Amano, J. Tromp, P. Vitanyi, and O. Watanabe
On a generalized ruin problem

Andrea E.F. Clementi and Pilu Crescenzi and Angelo Monti and Paolo Penna and Riccardo Silvestri
On Computing Ad-hoc Selective Families

Noga Alon and Michael Capalbo and Yoshiharu Kohayakawa and Vojtech Rodl and Andrzej Rucinski and Endre Szemeredi
Near-optimum universal graphs for graphs with bounded degrees

Sung-woo Cho and Ashish Goel
Exact Sampling in Machine Scheduling Problems

Adam R. Klivans
On the Derandomization of Constant Depth Circuits

John Dunagan and Santosh Vempala
On Euclidean Embeddings and Bandwidth Minimization

Sriram V. Pemmaraju
Equitable Coloring Extends Chernoff-Hoeffding Bounds