## What the Meeting is About

Appol 2 is a thematic network of the European Union, focussing on on-line and approximation algorithms. The Appol network consists of 15 universities.

The format of this meeting will be about two, two and a half days of lectures, followed by a few days during which research problems will be discussed in a congenial atmosphere.

## Tentative Schedule

TBA
23 24 Thomas Erlebach Frits Spieksma Alexander Hall Leen Stougie Martin Skutella Sai Anand Fernandez Dela Vega Guochuan Zhang Gerold Jäger Rene Sitters Stefano Leonardi

## Important Dates

Arrival: Saturday 22 March, 2003 Departures: 28-29 March, 2003
Last day of talks: Tuesday 25 March, 2003
End of workshop: Friday 28 March, 2003

## Location

The meeting will be held in the small medieval hilltop town of Bertinoro. This town is in Emilia Romagna about 50km east of Bologna at an elevation of about 230m.  Here is a map putting it in context. It is easily reached by train and taxi from Bologna and is close to many splendid Italian locations such as Ravenna, a treasure trove of byzantine art and history, and the Republic of San Marino (all within 35km) as well as some less well-known locations like the thermal springs of Fratta Terme and the castle and monastic gardens of Monte Maggio.  Bertinoro can also be a base for visiting some of the better-known Italian locations such as Padua, Ferrara, Vicenza, Venice, Florence and Siena.

Bertinoro itself is picturesque, with many narrow streets and walkways winding around the central peak.  The meeting will be held in a redoubtable ex-Episcopal fortress that has been converted by the University of Bologna into a modern conference center with computing facilities and Internet access.  From the fortress you can enjoy a beautiful the vista that stretches from the Tuscan Apennines to the Adriatic coast.

## List of confirmed participants so far. More can join later.

• Susanne Albers, Universität Freiburg
• Sai Anand, ETH Zürich
• Georg Baier, Technische Universität Berlin
• Euripides Bampis, Universitè D'Evry
• Debora Donato, Università La Sapienza di Roma
• Fabian Ennecke , ETH Zürich
• Thomas Erlebach, ETH Zürich
• Wenceslas Fernandez De La Vega, Universitè Paris-Sud
• Amos Fiat, University of Tel Aviv
• Alexander Hall, ETH Zürich
• Gerold Jäger, Universität Kiel
• Klaus Jansen, Universität Kiel
• Miklos Kresz, University of Szeged
• Stefano Leonardi, Università La Sapienza di Roma
• Alberto Marchetti Spaccamela, Università La Sapienza di Roma
• Ioannis Milis, Athens University of Economics and Business
• Marc Nunkesser, ETH Zürich
• Alessandro Panconesi, Università La Sapienza di Roma
• Rene Sitters, Technische Universiteit Eindhoven
• Martin Skutella, Technische Universität Berlin
• Ines Spenke, Technische Universität Berlin
• Frits Spieksma, Katholieke Universiteit Leuven
• Leen Stougie, Technische Universiteit Eindhoven
• Gabor Szabo, ETH Zürich
• Joris van de Klundert, Universiteit Maastricht
• Peter Widmayer, ETH Zürich
• Guochuan Zhang, Universität Kiel

Scientific Organizing Committee Stefano Leonardi Università La Sapienza di Roma Alessandro Panconesi Università La Sapienza di Roma Andrea Bandini, Elena Della Godenza, Centro Congressi di Bertinoro BICI   Bertinoro International Center for Informatics

### ABSTRACTS

On Paging with Locality of Reference
by Susanne Albers, Universität Freiburg

Motivated by the fact that competitive analysis yields too pessimistic results when applied to the paging problem, there has been considerable research interest in refining competitive analysis and in developing alternative models for studying online paging. The goal is to devise models in which theoretical results capture phenomena observed in practice. In this talk we propose a new, simple model for studying paging with locality of reference. The model is closely related to Denning's working set concept and directly reflects the amount of locality that request sequences exhibit. We demonstrate that our model is reasonable from a practical point of view. We use the page fault rate to evaluate the quality of paging algorithms, which is the performance measure used in practice. We develop tight or nearly tight bounds on the fault rates achieved by popular paging algorithms such as LRU, FIFO, deterministic Marking strategies and LFD. It shows that LRU is an optimal online algorithm, whereas FIFO and Marking strategies are not optimal in general. We present an experimental study comparing the page fault rates proven in our analyses to the page fault rates observed in practice. This is the first such study for an alternative/refined paging model.

(Joint work with Lene Favrholdt and Oliver Giel.)

A Linear Bound on the Diameter of the Transportation Polytope
by Leen Stougie, Technische Universiteit Eindhoven

We prove that the combinatorial diameter of the skeleton of the polytope of feasible solutions of any $m \times n$ transportation problem is less than $8 \, (m+n)$.

A competitive algorithm for the general two server-problem
by Rene Sitters, Technische Universiteit Eindhoven

We consider the general on-line two server problem in which at each step both servers receive a request, which is a point in a metric space. One of the servers has to be moved to its request. The special case where the requests are points on the real line is known as the CNN-problem. It has been a well-known open question if an algorithm with a constant competitive ratio exists for this problem. We answer this question in the affirmative sense by providing an algorithm that is 23808-competitive on any metric space. The constant is huge and the algorithm is rather ugly but our main goal was indeed to settle the question. We believe that our result gives new insight in the problem and will lead to more and much better algorithms for the general $k$-server problem in the near future.

Joint work with Leen Stougie and Willem de Paepe.

Polynomial time approximation schemes for metric MIN-BISECTION
by Fernandez De La Vega, Universitè Paris Sud

We design the first polynomial time approximation schemes (PTASs) for the problem of Metric MIN-BISECTION: given a finite metric space, divide the points into two halves so as to minimize the sum of distances across that partition. Our approximation schemes depend on biased sampling and on a new application of linearized quadratic programs with randomized rounding of non-uniformly bounded numbers.

Joint work with Marek Karpinski and Claire Kenyon

Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
by Stefano Leonardi, Università di Roma La Sapienza

Spielman and Teng invented the concept of smoothed analysis to explain the success of algorithms that are known to work well in practice while presenting poor worst case performance. Spielman and Teng [STOC 01] proved that the simplex algorithm runs in expected polynomial time if the input instance is smoothened with a normal distribution. We extend this notion to analyze online algorithms. In particular we introduce smoothed competitive analysis to study the Multi-Level Feedback (MLF) algorithm, at the basis of the scheduling policies of Unix and Windows NT, when the processing times of jobs released over time are only known at time of completion.

We show that, if the k least significant of K bits describing the processing time of a job are randomly changed, MLF achieves a tight smoothed competitive ratio of O(2K-k) to minimize the average flow time. A direct consequence is a first constant approximation for this problem in the average case under a quite general class of probability distributions.

Joint work with L. Becchetti, A. Marchetti-Spaccamela, G. Schäfer, and T. Vredeveld.

Approximating minimum cuts for valid paths in the Internet
by Thomas Erlebach, ETH Zürich

A recently proposed model of the Internet at the level of autnomous systems (ASs) is a graph in which the edges are classified according to the economic relationships between the ASs that they connect: Edges can be customer-provider edges or peer-to-peer edges. It is assumed that a path in the network is only valid if it consists of a sequence of customer-provider edges, followed by zero or one peer-to-peer edges, followed by a sequence of provider-customer edges. Motivated by robustness considerations, we consider the problem of computing a minimum vertex cut that separates two given vertices (meaning that no valid path between them remains after removing the vertices of the cut from the network). We show that the problem is NP-hard and present a 2-approximation algorithm based on linear programming techniques.

Flows over time - approximation and complexity
by Martin Skutella, Technische Universität Berlin

The intention of the talk is to give an introduction into the area of "flows over time" or "dynamic flows". Flows over time have been introduced about forty years ago by Ford and Fulkerson and have many real-world applications such as, for example, traffic control, evacuation plans, production systems, communication networks, and financial flows. Flows over time are modeled in networks with capacities and transit times on the arcs. The transit time of an arc specifies the amount of time it takes for flow to travel from the tail to the head of that arc. In contrast to the classical case of static flows, a flow over time specifies a flow rate entering an arc for each point in time and the capacity of an arc limits the rate of flow into the arc at each point in time. We discuss recent approximation and hardness results for flows over time with multiple commodities and costs. The talk is based on joint work with Lisa Fleischer, Alex Hall, and Steffen Hippler.

Routing and Call Control Algorithms in Ring Networks
by Sai Anand, ETH Zürich

FPTAS for Flows Over Time with Inflow-Dependent Transit Times
by Alexander Hall, ETH Zürich

Motivated by applications in road traffic control, we study flows in networks featuring special characteristics. In contrast to classical static flow problems, time plays an important role. Firstly, there are transit times on the arcs of the network which specify the amount of time it takes for flow to travel through an arc; in particular, flow values on arcs may change over time. Secondly, the transit time of an arc varies with the current amount of flow using this arc. The latter feature is crucial for various real-life applications of flows over time.

K\"ohler et al. (Proceedings of ESA 2002, LNCS 2461, pp. 599-611) study the single commodity case and give a (2+$\varepsilon$)-approximation based on the notion of temporarily repeated flows, where flow is pushed at constant rates into (possibly) several paths which do not change over time. We are able to generalize this result to the multicommodity case, by modifying the underlying network and the way flow is pushed into the corresponding paths. Applying the same technique to condensed time-expanded networks allows variation of flow paths over time. This approach even yields a fully polynomial time approximation scheme for the multicommodity case, which is known to be NP-hard. Furthermore we show that under a certain restriction of valid flows, the single commodity case is NP-hard as well.

Approximation of a retrieval problem for parallel disks
by Frits Spieksma, Katholieke Universiteit Leuven

When handling large collections of data, the communication between fast internal memory and slow external memory (e.g. disks) can be a performance bottleneck. We study the problem of maximizing the throughput (that is, the number of requests served per time-unit) for parallel disks. This retrieval problem can be formulated as assigning a maximum number of size 1 and size 2 jobs to machines of limited capacity. We show that the LP-relaxation of an integer programming formulation is half-integral. Further, we sketch 2/3-approximation algorithms for this problem.

Joint work with Joep Aerts and Jan Korst.

Improved Approximation Algorithms for Maximum Graph Partition Problems
by Gerold Jäger, Universität Kiel

Joint work with Anand Srivastav

We consider a weighted, directed graph with n vertices and the problem of dividing the set of vertices in two parts of sizes k and n-k, so that the edges of some of four regions (edges on the two subgraphs and edges between the two subgraphs in both directions) becomes maximum. For example, MAX-k-DENSE-SUBGRAPH is the problem of determining a subset S of size k, so that the sum of the edge weights of the subgraph induced by S becomes maximum. There are six nontrivial problems of this kind.

Halperin and Zwick have introduced an algorithm based on semidefinite programming, which for the case k = n/2 and these six maximum graph partition problems delivers the best known approximation ratios. We show improvements of their techniques and generalize the algorithm for arbitrary k.

On weighted rectangle packing
by Guochuan Zhang, Universität Kiel

Joint work with Klaus Jansen.

Approximation algorithms for max-min resource sharing, with an application to fractional weighted graph coloring
by Klaus Jansen, Universität Kiel

We generalize a method by Grigoriadis et al. to compute an approximate solution of the max-min resource sharing (and fractional covering) problem with $M$ nonnegative concave (linear) constraints $f_m$ on a convex set $B$ to the case with general approximate block solvers (i.e. with only constant, logarithmic, or even worse approximation ratios). The algorithm is based on a Lagrangian decomposition which uses a modified logarithmic potential function and on several other ideas (scaling phase strategy, two stopping rules in a phase, eliminating functions $f_m$ larger than a threshold value $T$, reducing the step length and taking a convex combination among different iterates in a phase). We show that the algorithm runs in $O(M \epsilon^{-2} \ln (M \epsilon^{-1}))$ iterations (or block optimization steps), a data and approximation ratio independent bound. Furthermore we show how to use this framework for the fractional weighted graph coloring problem.