APPOL 2 Workshop 23-28 March 2003
University of Bologna Residential Center |
---|
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.
08.00-09.00 | breakfast | |||||
---|---|---|---|---|---|---|
09.30-10.10 | Thomas Erlebach | Frits Spieksma | research! | research! | research! | departures |
10.15-11.05 | Alexander Hall | Leen Stougie | ||||
11.05-11.20 | coffee break | coffee break | ||||
11.20-12.00 | Martin Skutella | Sai Anand | ||||
12.30-13.30 | lunch! | lunch! | ||||
16.00-16.40 | Fernandez Dela Vega | Guochuan Zhang | ||||
16.45-17.35 | Gerold Jäger | Rene Sitters | ||||
17.35-17.50 | coffee | coffee | ||||
17.50-18.40 | Stefano Leonardi |
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 |
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.
Scientific Organizing Committee | Stefano Leonardi Università La Sapienza di Roma |
---|---|
Alessandro Panconesi Università La Sapienza di Roma | |
Local Organization | |
Andrea Bandini, Elena Della Godenza, Centro Congressi di Bertinoro | |
Sponsored by | BICI Bertinoro International Center for Informatics |
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.)
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)$.
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.
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
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.
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.
(joint work with Danica Vukadinovic)
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.
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.
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.
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.
Joint work with Klaus Jansen.
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.