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